Java深度優先和廣度優先遍歷怎么使用

這篇文章主要介紹“Java深度優先和廣度優先遍歷怎么使用”，在日常操作中，相信很多人在Java深度優先和廣度優先遍歷怎么使用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java深度優先和廣度優先遍歷怎么使用”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

#遍歷

圖的遍歷，所謂遍歷，即是對結點的訪問。一個圖有那么多個結點，如何遍歷這些結點，需要特定策略，一般有兩種訪問策略：

• 深度優先遍歷

• 廣度優先遍歷 #深度優先

深度優先遍歷，從初始訪問結點出發，我們知道初始訪問結點可能有多個鄰接結點，深度優先遍歷的策略就是首先訪問第一個鄰接結點，然后再以這個被訪問的鄰接結點作為初始結點，訪問它的第一個鄰接結點。總結起來可以這樣說：每次都在訪問完當前結點后首先訪問當前結點的第一個鄰接結點。 我們從這里可以看到，這樣的訪問策略是優先往縱向挖掘深入，而不是對一個結點的所有鄰接結點進行橫向訪問。 具體算法表述如下：

1. 訪問初始結點v，并標記結點v為已訪問。

2. 查找結點v的第一個鄰接結點w。

3. 若w存在，則繼續執行4，否則算法結束。

4. 若w未被訪問，對w進行深度優先遍歷遞歸（即把w當做另一個v，然后進行步驟123）。
   查找結點v的w鄰接結點的下一個鄰接結點，轉到步驟3。
   例如下圖，其深度優先遍歷順序為 1->2->4->8->5->3->6->7
   #廣度優先

類似于一個分層搜索的過程，廣度優先遍歷需要使用一個隊列以保持訪問過的結點的順序，以便按這個順序來訪問這些結點的鄰接結點。 具體算法表述如下：

1. 訪問初始結點v并標記結點v為已訪問。

2. 結點v入隊列

3. 當隊列非空時，繼續執行，否則算法結束。

4. 出隊列，取得隊頭結點u。

5. 查找結點u的第一個鄰接結點w。

6. 若結點u的鄰接結點w不存在，則轉到步驟3；否則循環執行以下三個步驟：
   1). 若結點w尚未被訪問，則訪問結點w并標記為已訪問。
   2). 結點w入隊列
   3). 查找結點u的繼w鄰接結點后的下一個鄰接結點w，轉到步驟6。
   如下圖，其廣度優先算法的遍歷順序為：1->2->3->4->5->6->7->8
   

package com.lifeibigdata.algorithms.graph.liantongfenliang;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by leofei.li on 2016/5/21.
 */
public class BFS {
    static int verNum;
    static boolean []visited;
    static String []ver={"A","B","C","D","E"};
    static int  [][]edge;

    void addEdge(int i,int j){
        if(i == j)return;
        edge[i][j]=1;
        edge[j][i]=1;
    }

    void dfsTraverse(){
        visited = new boolean[verNum];
        for(int i = 0; i< verNum; i ++){
            if(visited[i] == false){
                dfs(i);
            }
        }
    }
    void dfs(int i){
        visited[i] = true;
        System.out.print(ver[i] + " ");
        for(int j = 0; j < verNum; j++){
            if(visited[j] == false && edge[i][j] == 1){
                dfs(j);
            }
        }
    }

    void bfsTraverse(){
        visited = new boolean[verNum];
        Queue<Integer> quene = new LinkedList<Integer>();
        for (int i = 0; i < verNum; i ++){
            if(visited[i] == false){
                visited[i] = true;
                System.out.print(ver[i]+" ");
                quene.add(i);           //此處存儲的是索引
                while (!quene.isEmpty()){ //注意結束條件
                    int j = quene.poll();
                    for (int k = 0; k < verNum; k++){    //找到該節點所有的子節點
                        if(edge[j][k] == 1 && visited[k] == false){
                            visited[k] = true;
                            System.out.print(ver[k]+" ");
                            quene.add(k);
                        }
                    }
                }
            }
        }
    }

    void con(){
        int count = 0;
        visited = new boolean[verNum];
        for(int i = 0; i < verNum; i ++){
            if(!visited[i]){
                count++;
                dfsTraverse();
            }
        }
        System.out.println("共有"+count+"個連通分量!");
    }

    public static void main(String[] args) {
        verNum = ver.length;
        edge = new int[verNum][verNum];
        for(int i=0;i<verNum;i++){
            for (int j=0;j<verNum;j++){
                edge[i][j]=0;
            }
        }
        BFS b = new BFS();
        b.addEdge(0, 3);
        b.addEdge(0, 4);
        b.addEdge(1, 2);
        b.addEdge(2, 4);
        b.addEdge(2, 3);

        System.out.println("圖的深度遍歷操作:");
        b.dfsTraverse();
        System.out.println();
        System.out.println("圖的廣度遍歷操作：");
        b.bfsTraverse();
        System.out.println();
        System.out.println("連通分量:");
        b.con();
    }
}

不管深搜還是廣搜都需要申請總節點個數長度的數組用來標記節點是否訪問過(訪問數組)；深搜是遍歷訪問數組，從某個未被訪問的節點輻射出去，每次輻射結束后，判斷訪問數組中是否還有未被訪問的節點，如果有，再次輻射，如果沒有，深搜結束；廣搜是同樣是遍歷數組，判斷是否有為被訪問的節點，如果有放到對列中，然后彈出隊列，將彈出節點所有未被訪問的鄰接節點放到隊列中，繼續進行訪問隊列，直到隊列為空時繼續判斷訪問數組

到此，關于“Java深度優先和廣度優先遍歷怎么使用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！