資料結構與算法之圖的深度優先周遊和廣度優先周遊

圖是表示一種多對多關系的資料結構

它包括無向圖，有向圖，帶權圖

無向圖：就是頂點之間的連線（邊）沒有方向箭頭

有向圖：就是頂點之間的連線（邊）有方向箭頭

帶權圖：就是頂點之間的連線（邊）表明了大小如上海到北京的距離，北京到天津的距離類似的導航地圖就是帶權圖

下圖就是一個無向圖：

字母所表示的是頂點，頂點間的連線叫做邊

按照A,B,C,D,E,F,G的順序添加節點，并添加對應的邊構成下圖

深度優先周遊：

從初始通路結點出發，我們知道初始通路結點可能有多個鄰接結點，深度優先周遊的政策就是首先通路第一個鄰接結點，然後再以這個被通路的鄰接結點作為初始結點，通路它的第一個鄰接結點。總結起來可以這樣說：每次都在通路完目前結點後首先通路目前結點的第一個鄰接結點。

具體算法表述如下：

1.通路初始結點v，并标記結點v為已通路。

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

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

4.若w未被通路，對w進行深度優先周遊遞歸（即把w當做另一個v，然後進行步驟123）。

5.查找結點v的w鄰接結點的下一個鄰接結點，轉到步驟3。

按照上圖便利的順序應該是A->B->C->G->D->E->F->

廣度優先周遊：

類似于一個分層搜尋的過程，廣度優先周遊需要使用一個隊列以保持通路過的結點的順序，以便按這個順序來通路這些結點的鄰接結點。

具體算法表述如下：

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。

按照上圖便利的順序應該是A->B->C->D->E->G->F->

java代碼實作:

package com.yg.graph;/*
@date    2020/3/15  9:58
*/

import java.time.chrono.IsoChronology;
import java.util.*;

public class Graph {
    //存放頂點
    private List<String> vertexList;
    //表示頂點之間是否相連 0不連通，1連通
    private int[][] edges;
    //表示邊的數量
    private int numOfEdges = 0;
    //表示周遊時是否已經通路過
    private boolean[] isVisited;

    public static void main(String[] args) {
        //建構圖
        //添加頂點
        String[] vertexs = {"A", "B", "C", "D", "E","F","G"};
        Graph graph = new Graph(vertexs.length);
        for (String vertex : vertexs) {
            graph.addVertex(vertex);
        }
        //添加邊
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 1);
        graph.addEdge(3, 4, 1);
        graph.addEdge(4, 5, 1);
        graph.addEdge(2, 6, 1);
        graph.showGraph();
        //深度優先周遊
       // graph.dfs(0);

        //廣度優先周遊
       graph.bfs(0);
    }

    public Graph(int n) {
        vertexList = new ArrayList<>(n);
        edges = new int[n][n];
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    //深度優先周遊,index目前周遊的頂點
    private void dfs(int index) {
        //列印目前頂點
        System.out.print(vertexList.get(index)+"->");
        isVisited[index]=true;
        //得到第一個鄰接頂點
        int w=getFristNeighbor(index);
        //鄰接頂點存在
        while (w != -1) {
            if (!isVisited[w]) {
            dfs(w);
            }
            w=getNextNeighbor(index,w);
        }

    }

    //重載dfs
    public void dfs() {
        //這是為了預防有向圖中部分節點到不了的情況
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(i);
            }
        }
    }

    //廣度優先周遊
    private void bfs(int index) {
        //記錄節點通路順序
        Queue queue=new LinkedList();
        System.out.print(vertexList.get(index)+"->");
        isVisited[index]=true;
        queue.add(index);
        while (!queue.isEmpty()) {
            //隊列頭節點下表
            int vertexIndex= (int) queue.poll();
            //得到第一個鄰接頂點的下标
            int fristNeighbor = getFristNeighbor(vertexIndex);
            //是否還有鄰近頂點
            while (fristNeighbor != -1) {
                //是否通路過
                if (!isVisited[fristNeighbor]) {
                    System.out.print(vertexList.get(fristNeighbor)+"->");
                    isVisited[fristNeighbor]=true;
                    //入隊
                    queue.add(fristNeighbor);
                }
                fristNeighbor=getNextNeighbor(vertexIndex,fristNeighbor);
            }
        }

    }

    //重載bfs
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(i);
            }
        }
    }

    //得到目前頂點的第一個鄰接頂點,index目前頂點的下标
    public int getFristNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    //得到目前頂點鄰接頂點的下一個頂點
    public int getNextNeighbor(int index,int neighborIndex) {
        for (int i =neighborIndex+1; i <vertexList.size() ; i++) {
            if (edges[index][i]>0) {
                return i;
            }
        }
        return -1;
    }
    //添加頂點
    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    //添加邊
    /*
     * @param val1 頂點的下标，第幾個添加的頂點，小标從0開始
     * @param val2
     * @param weight  權重，為1表明有邊，0表示沒邊
     * @return : void
     * @date : 2020/3/15 10:05
     */
    public void addEdge(int val1, int val2, int weight) {
        edges[val1][val2] = weight;
        edges[val2][val1] = weight;
        numOfEdges++;
    }

    //得到頂點數量
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //得到邊的數量
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //列印圖
    public void showGraph() {
        for (int[] vertex : edges) {
            System.out.println(Arrays.toString(vertex));
        }
    }

}