廣度優先搜尋（BFS）思路及演算法分析
摘要：
1、演算法用途：
是一種影象搜尋演演算法。用於遍歷圖中的節點，有些類似於 樹的深度優先遍歷。這裡唯一的問題是，與樹不同，圖形可能包含迴圈，因此我們可能會再次來到同一節點。
2、主要思想：
主要藉助一個佇列、一個布林型別陣列、鄰接矩陣完成（判斷一個點是否檢視過，用於避免重複到達同...
1、演算法用途：
是一種影象搜尋演演算法。用於遍歷圖中的節點，有些類似於 樹的深度優先遍歷。這裡唯一的問題是，與樹不同，圖形可能包含迴圈，因此我們可能會再次來到同一節點。
2、主要思想：
主要藉助一個佇列、一個布林型別陣列、鄰接矩陣完成（判斷一個點是否檢視過，用於避免重複到達同一個點，造成死迴圈等），先將各點以及各點的關係存入鄰接矩陣。
再從第一個點開始，將一個點存入佇列，然後在鄰接表中找到他的相鄰點，存入佇列，每次pop出佇列頭部並將其打印出來（文字有些抽象，實際過程很簡單），整個過程有點像往水中投入石子水花散開。
（鄰接表是表示了圖中與每一個頂點相鄰的邊集的集合，這裡的集合指的是無序集）
3、程式碼（java）：
(以上圖為例的程式碼）
1 import java.util.*;
2
3 //This class represents a directed graph using adjacency list
4 //representation
5 class Graph1 {
6private static int V; // No. of vertices
7private LinkedList<Integer> adj[]; // Adjacency Lists
8
9// Constructor
10Graph1(int v) {
11V = v;
12adj = new LinkedList[v];
13for (int i = 0; i < v; ++i)
14adj[i] = new LinkedList();
15}
16
17// Function to add an edge into the graph
18void addEdge(int v, int w) {
19adj[v].add(w);
20}
21
22// prints BFS traversal from a given source s
23public void BFS() {
24// Mark all the vertices as not visited(By default
25// set as false)
26boolean visited[] = new boolean[V];
27// Create a queue for BFS
28LinkedList<Integer> queue = new LinkedList<Integer>();
29
30for (int i = 0; i < V; i++) {
31if (!visited[i]) {
32BFSUtil(i, visited, queue);
33}
34}
35}
36
37public void BFSUtil(int s, boolean visited[], LinkedList<Integer> queue) {
38// Mark the current node as visited and enqueue it
39visited[s] = true;
40queue.add(s);
41
42while (queue.size() != 0) {
43// Dequeue a vertex from queue and print it
44s = queue.poll();
45System.out.print(s + " ");
46
47// Get all adjacent vertices of the dequeued vertex s
48// If a adjacent has not been visited, then mark it
49// visited and enqueue it
50Iterator<Integer> i = adj[s].listIterator();
51while (i.hasNext()) {
52int n = i.next();
53if (!visited[n]) {
54visited[n] = true;
55queue.add(n);
56}
57}
58}
59}
60
61// Driver method to
62public static void main(String args[]) {
63Graph1 g = new Graph1(4);
64
65g.addEdge(0, 1);
66g.addEdge(0, 2);
67g.addEdge(1, 2);
68g.addEdge(2, 0);
69g.addEdge(2, 3);
70g.addEdge(3, 3);
71
72System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");
73g.BFS();
74}
75 }
4、複雜度分析：
演算法藉助了一個鄰接表和佇列，故它的空問複雜度為O(V）。 遍歷圖的過程實質上是對每個頂點查詢其鄰接點的過程，其耗費的時間取決於所採用結構。 鄰接表表示時，查詢所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間複雜度為O(V+E)。