Java數(shù)據(jù)結(jié)構(gòu)中圖的示例分析

這篇文章給大家分享的是有關(guān)Java數(shù)據(jù)結(jié)構(gòu)中圖的示例分析的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

有向圖

有向圖的定義及相關(guān)術(shù)語

定義∶ 有向圖是一副具有方向性的圖，是由一組頂點和一組有方向的邊組成的，每條方向的邊都連著 一對有序的頂點。

出度∶ 由某個頂點指出的邊的個數(shù)稱為該頂點的出度。

入度: 指向某個頂點的邊的個數(shù)稱為該頂點的入度。

有向路徑︰ 由一系列頂點組成，對于其中的每個頂點都存在一條有向邊，從它指向序列中的下一個頂點。

有向環(huán)∶ —條至少含有一條邊，且起點和終點相同的有向路徑。

一副有向圖中兩個頂點v和w可能存在以下四種關(guān)系:

1.沒有邊相連;

⒉存在從v到w的邊v—>w;

3.存在從w到v的邊w—>V;

4.既存在w到v的邊，也存在v到w的邊，即雙向連接;

理解有向圖是一件比較簡單的，但如果要通過眼睛看出復(fù)雜有向圖中的路徑就不是那么容易了。

有向圖API設(shè)計

 在api中設(shè)計了一個反向圖，其因為有向圖的實現(xiàn)中，用adj方法獲取出來的是由當(dāng)前頂點v指向的其他頂點，如果能得到其反向圖，就可以很容易得到指向v的其他頂點。

有向圖的實現(xiàn)

// 有向圖
 
public class Digraph {
    // 記錄頂點的數(shù)量
     
    private final int V;
 
    //記錄邊的數(shù)量
    private int E;
 
    //定義有向圖的鄰接表
    private Queue <Integer>[] adj;
 
    public Digraph (int v) {
        //初始化頂點數(shù)量
        this.V = v;
        //初始化邊的數(shù)量
        this.E = 0;
        //初始化鄰接表
        adj = new LinkedList[v];
        //初始化鄰接表的空隊列
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }
    public int V () {
        return V;
    }
    public int E () {
        return E;
    }
 
    //添加一條 v -> w的有向邊
    public void addEage (int v , int w) {
        adj[v].add(w);
        ++E;
    }
 
    //獲取頂點v 指向的 所有頂點
    public Queue<Integer> adj (int v) {
        return adj[v];
    }
 
    //將有向圖 反轉(zhuǎn) 后返回
    public Digraph reverse () {
        //創(chuàng)建一個反向圖
        Digraph reverseDigraph = new Digraph(V);
        //獲取原來有向圖的每個結(jié)點
        for (int i = 0; i < V; i++) {
            //獲取每個結(jié)點 鄰接表的所有結(jié)點
            for (Integer w : adj[i]) {
                //反轉(zhuǎn)圖記錄下 w -> v
                reverseDigraph.adj(w).add(i);
            }
        }
        return reverseDigraph;
    }
}

拓?fù)渑判?/h3>

在現(xiàn)實生活中，我們經(jīng)常會同一時間接到很多任務(wù)去完成，但是這些任務(wù)的完成是有先后次序的。以我們學(xué)習(xí)java學(xué)科為例，我們需要學(xué)習(xí)很多知識，但是這些知識在學(xué)習(xí)的過程中是需要按照先后次序來完成的。從java基礎(chǔ)，到j(luò)sp/servlet，到ssm，到springboot等是個循序漸進且有依賴的過程。在學(xué)習(xí)jsp前要首先掌握java基礎(chǔ)和html基礎(chǔ)，學(xué)習(xí)ssm框架前要掌握jsp/servlet之類才行。

 為了簡化問題，我們使用整數(shù)為頂點編號的標(biāo)準(zhǔn)模型來表示這個案例:

此時如果某個同學(xué)要學(xué)習(xí)這些課程，就需要指定出一個學(xué)習(xí)的方案，我們只需要對圖中的頂點進行排序，讓它轉(zhuǎn)換為一個線性序列，就可以解決問題，這時就需要用到一種叫拓?fù)渑判虻乃惴ā?/p>

拓?fù)渑判驁D解

給定一副有向圖，將所有的頂點排序，使得所有的有向邊均從排在前面的元素指向排在后面的元素，此時就可以明確的表示出每個頂點的優(yōu)先級。下列是一副拓?fù)渑判蚝蟮氖疽鈭D︰

檢測有向圖中的環(huán)

如果學(xué)習(xí)x課程前必須先學(xué)習(xí)y課程，學(xué)習(xí)y課程前必須先學(xué)習(xí)z課程，學(xué)習(xí)z課程前必須先學(xué)習(xí)x課程，那么一定是有問題了，我們就沒有辦法學(xué)習(xí)了，因為這三個條件沒有辦法同時滿足。其實這三門課程x、y、z的條件組成了一個環(huán)︰

因此，如果我們要使用拓?fù)渑判蚪鉀Q優(yōu)先級問題，首先得保證圖中沒有環(huán)的存在。

檢測有向環(huán)的API設(shè)計

檢測有向環(huán)實現(xiàn)

在API中添加了onStack[]布爾數(shù)組，索引為圖的頂點，當(dāng)我們深度搜索時︰

1.在如果當(dāng)前頂點正在搜索，則把對應(yīng)的onStack數(shù)組中的值改為true，標(biāo)識進棧;

2.如果當(dāng)前頂點搜索完畢，則把對應(yīng)的onStack數(shù)組中的值改為false，標(biāo)識出棧;

3.如果即將要搜索某個頂點，但該頂點已經(jīng)在棧中，則圖中有環(huán);

代碼

 /**
 *  檢查圖中是否存在環(huán)
 */
public class DirectedCycle {
    /**
     * 索引代表頂點，用來記錄頂點是否被搜索過
     */
    private boolean[] marked;
 
    /**
     * 判斷圖中是否有環(huán)
     */
    private boolean hasCycle;
 
    /**
     * 采用棧的思想，記錄當(dāng)前頂點是否已經(jīng)存在 當(dāng)前搜索的的路徑上
     * 存在則可以判斷 圖中是存在環(huán)的
     */
    private boolean[] onStack;
 
    /**
     * 判斷傳入的有向圖 是否存在環(huán)
     * @param G
     */
    public DirectedCycle (Digraph G) {
        marked = new boolean[G.V()];
        onStack = new boolean[G.V()];
        hasCycle = false;
        //因為不知道從那個點出發(fā) 可能存在環(huán)
        //所以需要從所有的頂點都出發(fā)搜索 判斷是否存在環(huán)
        for (int i = 0; i < G.V(); i++) {
            dfs(G,i);
        }
    }
 
    /**
     * 采用深度搜索 判斷有向圖是否存在環(huán)
     * onStack 入棧出棧 然后判斷當(dāng)前搜索的頂點是否已經(jīng)在搜索路徑上
     *
     * @param G
     * @param v
     */
    private void dfs (Digraph G,int v) {
        //標(biāo)記頂點已經(jīng)搜索過
        marked[v] = true;
        for (Integer adj : G.adj(v)) {
            //判斷v 是否已經(jīng)在搜索的路徑上了
            if(marked[adj] && onStack[adj]) {
                //存在環(huán)
                hasCycle = true;
            }else {
                //采用回溯的思路
                //讓頂點入棧
                onStack[adj] = true;
                dfs(G,adj);
                //回溯 頂點出棧
                onStack[adj] = false;
            }
        }
    }
 
    /**
     * 判斷是否存在環(huán)
     * @return
     */
    public boolean hasCycle(){
        return hasCycle;
    }
 
}

基于深度優(yōu)先的頂點排序

如果要把圖中的頂點生成線性序列其實是一件非常簡單的事，之前我們學(xué)習(xí)并使用了多次深度優(yōu)先搜索，我們會發(fā)現(xiàn)其實深度優(yōu)先搜索有一個特點，那就是在一個連通子圖上，每個頂點只會被搜索一次，如果我們能在深度優(yōu)先搜索的基礎(chǔ)上，添加一行代碼，只需要將搜索的頂點放入到線性序列的數(shù)據(jù)結(jié)構(gòu)中，我們就能完成這件事。

頂點排序API設(shè)計

頂點排序?qū)崿F(xiàn)

在API的設(shè)計中，我們添加了一個棧reversePost用來存儲頂點，當(dāng)我們深度搜索圖時，每搜索完畢一個頂點，把該頂點放入到reversePost中，這樣就可以實現(xiàn)頂點排序。

代碼:

 /**
 * 深度優(yōu)先搜索 的頂點排序
 */
public class DepthFirstOrder {
    /**
     * 索引代表頂點 ，用來記錄頂點是否已經(jīng)被搜索過了
     */
    private boolean[] marked;
 
    /**
     * 使用棧記錄深度優(yōu)先搜索下的頂點
     */
    private Stack<Integer> reversePost;
 
    public DepthFirstOrder (Digraph G) {
        marked = new boolean[G.V()];
        reversePost = new Stack<>();
        for (int i = 0; i < G.V(); i++) {
            //如果頂點已經(jīng)被搜索過則不用
            if(!marked[i])
                dfs(G,i);
        }
    }
 
    /**
     * 基于深度優(yōu)先搜索，生成頂點線性序列
     * @param G
     * @param v
     */
    private void dfs (Digraph G, int v) {
        //標(biāo)記頂點已經(jīng)被搜索過
        marked[v] =  true;
        for (Integer w : G.adj(v)) {
            if(!marked[w])
                dfs(G,w);
        }
        //記錄到線性序列中
        reversePost.push(v);
    }
 
    /**
     * 獲取頂點線性序列
     * @return
     */
    private Stack<Integer> ReversePost() {
        return reversePost;
    }
}

感謝各位的閱讀！關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)中圖的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！