BFS
預先準備
- matrix二維陣列，1代表連起來(Connected)，0代表不能連。
visted[]陣列，判斷是否已訪問過。- Queue佇列
先把頂點0放入佇列，並設為已訪問，下圖中，箭頭入是放入佇列的方向，箭頭出是從佇列取出的方向。
| 頂點 | j=0 | j=1 | j=2 | j=3 |
| i=0 | 0 | 1 | 1 | 0 |
| i=1 | 1 | 0 | 0 | 1 |
| i=2 | 1 | 0 | 0 | 0 |
| i=3 | 0 | 1 | 0 | 0 |
| 頂點 | 0 | 1 | 2 | 3 |
| visted | F | F | F |
把頂點0從佇列取出來，印出頂點0。
查一下matrix表格中，第0列(i=0)代表頂點0，j是相連頂點，1代表相連，j=1與j=2的時候，是1，是相連的，把頂點1與頂點2放入佇列。
| 頂點 | j=0 | j=1 | j=2 | j=3 |
| i=0 | 0 | 1 | 1 | 0 |
並把頂點1與頂點2設為已訪問。
|頂點 |0|1|2|3|
|visted|T|F T|F T|F|
把頂點1從佇列取出，印出頂點1。
查一下matrix表格中，第1列(i=1)代表頂點1，j是相連頂點，1代表相連，j=0與j=3的時候，是1，是相連的，但頂點0已被訪問過，只放入未訪問頂點3放入佇列。
| 頂點 | j=0 | j=1 | j=2 | j=3 |
| i=0 | 0 | 1 | 1 | 0 |
| i=1 | 1 | 0 | 0 | 1 |
並把頂點3設為已訪問。
|頂點 |0|1|2|3|
|visted|T|T|T|F T|
把頂點2從佇列取出，印出頂點2。
把頂點3從佇列取出，印出頂點3。
完整程式碼如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.LinkedList;
public class BFS {
private int[][] matrix;
private int vertexLen = 4;
private boolean[] visted;
public BFS() {
matrix = new int[vertexLen][vertexLen];
matrix[0] = new int[]{0, 1, 1, 0};
matrix[1] = new int[]{1, 0, 0, 1};
matrix[2] = new int[]{1, 0, 0, 0};
matrix[3] = new int[]{0, 1, 0, 0};
visted = new boolean[vertexLen];
}
public void bfs() {
LinkedList<Integer> queue = new LinkedList<>();
// 因為可能會有頂點互相不連通，所以要使用for，確保每個頂點都訪問到。
for (int i = 0; i < vertexLen; i++) {
// 是否訪問過？
if (!visted[i]) {
// 沒訪問過才加入queue
queue.add(i);
// 設為已訪問
visted[i] = true;
}
// 若queue不為空就一直迴圈
while (!queue.isEmpty()) {
// 從queue取出頂點
int vertex = queue.poll();
// 印出頂點
System.out.print(vertex + "->");
// 檢查j欄(column)的頂點是否有相連
for (int j = 0; j < vertexLen; j++) {
// 沒有被訪問 並且相連
if (!visted[j] && matrix[vertex][j] == 1) {
// 加入queue
queue.add(j);
// 設為已訪問
visted[j] = true;
}
}
}
}
}
public static void main(String[] args) {
BFS bfs = new BFS();
bfs.bfs();
}
}
0->1->2->3->