Java深度優(yōu)先和廣度優(yōu)先遍歷怎么使用

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

#遍歷

圖的遍歷，所謂遍歷，即是對(duì)結(jié)點(diǎn)的訪問。一個(gè)圖有那么多個(gè)結(jié)點(diǎn)，如何遍歷這些結(jié)點(diǎn)，需要特定策略，一般有兩種訪問策略：

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

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

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

1. 訪問初始結(jié)點(diǎn)v，并標(biāo)記結(jié)點(diǎn)v為已訪問。

2. 查找結(jié)點(diǎn)v的第一個(gè)鄰接結(jié)點(diǎn)w。

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

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

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

1. 訪問初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問。

2. 結(jié)點(diǎn)v入隊(duì)列

3. 當(dāng)隊(duì)列非空時(shí)，繼續(xù)執(zhí)行，否則算法結(jié)束。

4. 出隊(duì)列，取得隊(duì)頭結(jié)點(diǎn)u。

5. 查找結(jié)點(diǎn)u的第一個(gè)鄰接結(jié)點(diǎn)w。

6. 若結(jié)點(diǎn)u的鄰接結(jié)點(diǎn)w不存在，則轉(zhuǎn)到步驟3；否則循環(huán)執(zhí)行以下三個(gè)步驟：
   1). 若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn)w并標(biāo)記為已訪問。
   2). 結(jié)點(diǎn)w入隊(duì)列
   3). 查找結(jié)點(diǎn)u的繼w鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6。
   如下圖，其廣度優(yōu)先算法的遍歷順序?yàn)椋?->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);           //此處存儲(chǔ)的是索引
                while (!quene.isEmpty()){ //注意結(jié)束條件
                    int j = quene.poll();
                    for (int k = 0; k < verNum; k++){    //找到該節(jié)點(diǎn)所有的子節(jié)點(diǎn)
                        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+"個(gè)連通分量!");
    }

    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();
    }
}

不管深搜還是廣搜都需要申請(qǐng)總節(jié)點(diǎn)個(gè)數(shù)長(zhǎng)度的數(shù)組用來標(biāo)記節(jié)點(diǎn)是否訪問過(訪問數(shù)組)；深搜是遍歷訪問數(shù)組，從某個(gè)未被訪問的節(jié)點(diǎn)輻射出去，每次輻射結(jié)束后，判斷訪問數(shù)組中是否還有未被訪問的節(jié)點(diǎn)，如果有，再次輻射，如果沒有，深搜結(jié)束；廣搜是同樣是遍歷數(shù)組，判斷是否有為被訪問的節(jié)點(diǎn)，如果有放到對(duì)列中，然后彈出隊(duì)列，將彈出節(jié)點(diǎn)所有未被訪問的鄰接節(jié)點(diǎn)放到隊(duì)列中，繼續(xù)進(jìn)行訪問隊(duì)列，直到隊(duì)列為空時(shí)繼續(xù)判斷訪問數(shù)組

到此，關(guān)于“Java深度優(yōu)先和廣度優(yōu)先遍歷怎么使用”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！