圖的遍歷——BFS

原創

裸一篇圖的BFS遍歷，直接來圖：

 簡單介紹一下BFS遍歷的過程：

　　以上圖為例子，從0開始遍歷，訪問0，按大小順序訪問與0相鄰的所有頂點，即先訪問1，再訪問2；

至此頂點0已經沒有作用了，因為其本身和與其所有相鄰的頂點都已被訪問，將其出隊列，我們用隊列

存儲已訪問過的頂點；然後順著隊列，訪問頂點1和所有與頂點1相鄰的頂點，這裡沒有，所有訪問頂點

2和所有與頂點2相鄰的結點，即3和4，註意，是先訪問3，再訪問4，因為採用鄰接矩陣來存儲圖。

Java:

import java.util.*;

public class 圖的遍歷_bfs {
    
    static int v;    //頂點數
    static int e;    //邊數
    static int array[][];    //鄰接矩陣
    static int book[];    //標記
    static int que[];    //隊列
    static int max=99999;    //無窮

    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        v=reader.nextInt();
        e=reader.nextInt();
        array=new int[v][v];
        book=new int[v];
        que=new int[v];
        //矩陣初始化
        for(int i=0;i<v;i++) {
            for(int j=0;j<v;j++) {
                if(i==j) {
                    array[i][j]=0;
                }
                else {
                    array[i][j]=max;
                }
            }
        }
        //讀入邊
        for(int i=0;i<e;i++) {
            int first_One=reader.nextInt();
            int second_Two=reader.nextInt();
            array[first_One][second_Two]=1;
            array[second_Two][first_One]=1;
        }
        int head=0;    //頭指針
        int tail=0;    //尾指針
        que[tail]=0;    //從頂點0開始遍歷
        book[0]=1;
        tail++;
        while(head<tail) {
            for(int i=0;i<v;i++) {
                if(array[ que[head] ][i]==1 && book[i]==0) {
                    que[tail]=i;    //加入隊列
                    tail++;
                    book[i]=1;
                }
                if(tail>v-1) {
                    break;
                }
            }
            head++;
        }
        for(int i=0;i<v;i++) {
            System.out.print(que[i]+" ");
        }
    }

}

測試用例：

輸入：

6 5
0 1
1 2
2 3
0 4
4 5

輸出：

0 1 4 2 5 3

22:34:03

2018-07-22