一、介紹

圖的DFS(深度優先搜索)與BFS(廣度優先搜索)是圖的兩種遍歷方式，

主要區別在于當到達圖中的一個頂點后，DFS直接到達其中的一個（未遍歷過的）頂點，之后再以這個新的頂點為基點重復上面的操作；而BFS到達圖中的一個頂點后，會先遍歷頂點周圍的所有（未遍歷過的）頂點，然后在以其中的一個頂點為基點，重復上面的操作，

舉個簡單的例子：
在這里插入圖片描述
如果分別用DFS和BFS進行遍歷（以A為起點）：
DFS：A B D E C (一條路走到頭)
BFS：A B C D E (先把A的周圍走完，接著走完B和C的周圍)

這篇文章將進行BFS的分析，前一篇文章分析DFS，

二、圖的建立

2.1建立圖類

使用鄰接矩陣保存圖的資訊，
為了給每個頂點起名字，使用了兩組map集合使頂點的名字與鄰接矩陣的數字一一對應，
用boolean型陣列記錄某節點是否被訪問過，

代碼：

class graph{
    int vertexNum;//頂點數
    int edgeNum;//邊數
    int[][] adjacentMatrix;//鄰接矩陣
    boolean[] isVisited;//各頂點是否被訪問

    Map<Character,Integer> nameToNum;
    Map<Integer,Character> numToName;
    int index;//頂點名稱的下標

    //建構式
    graph(int vertexnum, int edgenum){
        vertexNum = vertexnum;
        edgeNum = edgenum;
        adjacentMatrix = new int[vertexNum][vertexNum];
        nameToNum = new HashMap<>();
        numToName = new HashMap<>();
        isVisited = new boolean[vertexnum];
    }

    //頂點名稱
    public void addVertexName(char vertex){
        nameToNum.put(vertex,index);
        index++;
    }

    //反轉頂點和其索引的對應關系
    public void invertNameToNum(){
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
            numToName.put(nameToNum.get(c),c);
        }
    }

    //列印兩個map
    public void printMap(){
        System.out.println("name to num:");
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
            System.out.println(c + "->" + nameToNum.get(c));
        }
        System.out.println();
        System.out.println("num to name:");
        Set<Integer> ins = numToName.keySet();
        for (Integer in : ins) {
            System.out.println(in+"->"+ numToName.get(in));
        }

    }

    //添加邊
    public void addEdge(char vertex1, char vertex2, int weight){
        adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
        adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
    }

    //列印鄰接矩陣
    public void printAdjacentMatrix(){
        for (int[] am : adjacentMatrix) {
            for (int i : am) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
    
}

2.2建立圖

以下面的圖為例，建立圖結構，
在這里插入圖片描述
main方法中的代碼：

    public static void main(String[] args) {
        //while (true) {
        System.out.println("請輸入頂點數：");
        Scanner sc = new Scanner(System.in);
        int vertexNum = sc.nextInt();
        System.out.println("請輸入邊數：");
        int edgeNum = sc.nextInt();
        graph gr = new graph(vertexNum, edgeNum);

        for (int i = 0; i < vertexNum; i++) {
            System.out.println("請輸入第" + i + "個頂點的名稱：");
            gr.addVertexName(sc.next().charAt(0));//字串的第一個字符存入
        }
        gr.invertNameToNum();
        for (int i = 0; i < edgeNum; i++) {
            System.out.println("請輸入第" + i + "條邊(name1 name2 weight)：");
            gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);//無向圖權重為1，不用輸入
        }
        gr.printAdjacentMatrix();
	}

依次輸入相關資訊：
在這里插入圖片描述

出來的鄰接矩陣：

三、BFS

BFS方法使用佇列進行遍歷，
先將出發點壓入佇列，之后將其周圍的點壓入佇列，
出佇列的程序就是遍歷輸出的程序，
每次出佇列時，將其周圍的（未遍歷過的）頂點都入佇列，
當佇列中沒有元素了，就表明遍歷完成，

3.1圖解：

以A為起始點，將A的周圍頂點都入佇列（佇列=ABCD），A出佇列輸出A，A周圍的頂點都入佇列了，不用執行入佇列操作，
在這里插入圖片描述
此時佇列=BCD，B出佇列，輸出B，將B相鄰頂點E入佇列，

此時佇列=BCDE，C出佇列，輸出C，將C相鄰頂點F入佇列，

此時佇列=DEF，D出佇列，輸出D，將D相鄰頂點G入佇列，

此時佇列=EFG，E出佇列，輸出E，后面回圈這個操作，依次輸出E，F，G，
在這里插入圖片描述
輸出順序為：A B C D E F G，
代碼：

3.2代碼

graph類中的方法，

    public void BFS(){
        Queue<Integer> qu = new ArrayDeque<>();//創建佇列
        qu.add(0);//從第0開始訪問
        System.out.print(numToName.get(0)+ "->");
        isVisited[0] = true;
        while(!qu.isEmpty()){//佇列是否為非空
            int po = qu.poll();//出佇列
            int start = 0;
            while(start < vertexNum ){//將周圍的頂點（未標記過的）入佇列
                if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
                    qu.add(start);//入佇列
                    System.out.print(numToName.get(start)+"->");//輸出
                    isVisited[start] = true;//標記為訪問過
                }
                start++;
            }
        }
        System.out.println("結束");
    }

結果：A->B->C->D->E->F->G->結束

四、DFS和BFS完整代碼

package graph;
import java.util.*;

public class BFSAndDFS {
    public static void main(String[] args) {
        System.out.println("請輸入頂點數：");
        Scanner sc = new Scanner(System.in);
        int vertexNum = sc.nextInt();
        System.out.println("請輸入邊數：");
        int edgeNum = sc.nextInt();
        graph gr = new graph(vertexNum, edgeNum);

        for (int i = 0; i < vertexNum; i++) {
            System.out.println("請輸入第" + i + "個頂點的名稱：");
            gr.addVertexName(sc.next().charAt(0));//字串的第一個字符存入
        }
        gr.invertNameToNum();

        for (int i = 0; i < edgeNum; i++) {
            System.out.println("請輸入第" + i + "條邊(name1 name2 weight)：");
            gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);
        }
        gr.printAdjacentMatrix();
        gr.DFS();
        gr.BFS();
    }

}

class graph{
    int vertexNum;//頂點數
    int edgeNum;//邊數
    int[][] adjacentMatrix;//鄰接矩陣
    boolean[] isVisited;//各頂點是否被訪問

    Map<Character,Integer> nameToNum;
    Map<Integer,Character> numToName;
    int index;//頂點名稱的下標

    //建構式
    graph(int vertexnum, int edgenum){
        vertexNum = vertexnum;
        edgeNum = edgenum;
        adjacentMatrix = new int[vertexNum][vertexNum];
        nameToNum = new HashMap<>();
        numToName = new HashMap<>();
        isVisited = new boolean[vertexnum];
    }

    //頂點名稱
    public void addVertexName(char vertex){
        nameToNum.put(vertex,index);
        index++;
    }

    //反轉頂點和其索引的對應關系
    public void invertNameToNum(){
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
            numToName.put(nameToNum.get(c),c);
        }
    }

    //列印兩個map
    public void printMap(){
        System.out.println("name to num:");
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
            System.out.println(c + "->" + nameToNum.get(c));
        }
        System.out.println();
        System.out.println("num to name:");
        Set<Integer> ins = numToName.keySet();
        for (Integer in : ins) {
            System.out.println(in+"->"+ numToName.get(in));
        }

    }

    //添加邊
    public void addEdge(char vertex1, char vertex2, int weight){
        adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
        adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
    }

    //列印鄰接矩陣
    public void printAdjacentMatrix(){
        for (int[] am : adjacentMatrix) {
            for (int i : am) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 深度優先遍歷
     * @param index 頂點的索引
     */
    public void DFS(int index){
        System.out.print(numToName.get(index) + "->");
        isVisited[index] = true;
        int start = 0;
        while( start < vertexNum && (adjacentMatrix[index][start] == 0||(adjacentMatrix[index][start] != 0 && isVisited[start]))){
            start++;
        }

        if(start > vertexNum - 1){
            return;
        }

        DFS(start);
    }


    public void DFS(){
        for (int i = 0; i < vertexNum; i++) {
            if(!isVisited[i]){
                DFS(i);
            }
        }
        System.out.println("結束");
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
    }

    public void BFS(){
        Queue<Integer> qu = new ArrayDeque<>();//創建佇列
        qu.add(0);//從第0開始訪問
        System.out.print(numToName.get(0)+ "->");
        isVisited[0] = true;
        while(!qu.isEmpty()){
            int po = qu.poll();
            int start = 0;
            while(start < vertexNum ){
                if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
                    qu.add(start);
                    System.out.print(numToName.get(start)+"->");
                    isVisited[start] = true;
                }
                start++;
            }
        }
        System.out.println("結束");
    }

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/206818.html

標籤：python

上一篇：GIS拓撲關系原理詳解

下一篇：java中的clone方法的使用

圖：BFS(深度優先搜索)圖解分析代碼實作

文章目錄