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

創(chuàng)新互聯建站是專業(yè)的云岡網站建設公司，云岡接單;提供做網站、網站建設,網頁設計,網站設計,建網站,PHP網站建設等專業(yè)做網站服務;采用PHP框架,可快速的進行云岡網站開發(fā)網頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網站,專業(yè)的做網站團隊,希望更多企業(yè)前來合作!

#遍歷

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

• 深度優(yōu)先遍歷

• 廣度優(yōu)先遍歷 #深度優(yōu)先

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

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

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

3. 若w存在，則繼續(xù)執(zhí)行4，否則算法結束。

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

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

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

2. 結點v入隊列

3. 當隊列非空時，繼續(xù)執(zhí)行，否則算法結束。

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

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

6. 若結點u的鄰接結點w不存在，則轉到步驟3；否則循環(huán)執(zhí)行以下三個步驟：
   1). 若結點w尚未被訪問，則訪問結點w并標記為已訪問。
   2). 結點w入隊列
   3). 查找結點u的繼w鄰接結點后的下一個鄰接結點w，轉到步驟6。
   如下圖，其廣度優(yōu)先算法的遍歷順序為：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 quene = new LinkedList();
        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++){    //找到該節(jié)點所有的子節(jié)點
                        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
不管深搜還是廣搜都需要申請總節(jié)點個數長度的數組用來標記節(jié)點是否訪問過(訪問數組)；深搜是遍歷訪問數組，從某個未被訪問的節(jié)點輻射出去，每次輻射結束后，判斷訪問數組中是否還有未被訪問的節(jié)點，如果有，再次輻射，如果沒有，深搜結束；廣搜是同樣是遍歷數組，判斷是否有為被訪問的節(jié)點，如果有放到對列中，然后彈出隊列，將彈出節(jié)點所有未被訪問的鄰接節(jié)點放到隊列中，繼續(xù)進行訪問隊列，直到隊列為空時繼續(xù)判斷訪問數組
到此，關于“Java深度優(yōu)先和廣度優(yōu)先遍歷怎么使用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注創(chuàng)新互聯網站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>            
            
                        

            當前標題：Java深度優(yōu)先和廣度優(yōu)先遍歷怎么使用            

            標題來源：http://weahome.cn/article/gpipoj.html