[ Intro Alg ] Elementary Graph Algorithms - Breadth-first search

Preface: 
Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Prim’s minimum-spanning-tree algorithm (Section 23.2) and Dijkstra’s single-source shortest-paths algorithm (Section 24.3) use ideas similar to those in breadth-first search. 

Given a graph G=(V,E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a “breadth-first tree” with root s that contains all reachable vertices. For any vertex reachable from s, the simple path in the breadth-first tree from s to corresponds to a “shortest path” from s to in G, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs. 

To keep track of progress, breadth-first search colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. A vertex isdiscovered the first time it is encountered during the search, at which time it becomes nonwhite. Gray and black vertices, therefore, have been discovered, but breadth-first search distinguishes between them to ensure that the search proceeds in a breadth-first manner. 1 If (u,v) ∈ E and vertex u is black, then vertex v is either gray or black; that is, all vertices adjacent to black vertices have been discovered. Gray vertices may have some adjacent white vertices; they represent the frontier between discovered and undiscovered vertices. 

Breadth-first search constructs a breadth-first tree, initially containing only its root, which is the source vertex s. Whenever the search discovers a white vertex in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added to the tree. We say that u is the predecessor orparent of v in the breadth-first tree. Since a vertex is discovered at most once, it has at most one parent. Ancestor and descendant relationships in the breadth-first tree are defined relative to the root s as usual: if u is on the simple path in the tree from the root s to vertex v, then u is an ancestor of v and v is a descendant of u. 

The breadth-first-search procedure BFS below assumes that the input graph G=(V,E) is represented using adjacency lists. It attaches several additional attributes to each vertex in the graph. We store the color of each vertex u ∈ V in the attribute u.color and the predecessor of u in the attribute u.π If u has no predecessor , then u.π = NIL. The attribute u.d holds the distance from the source s to vertex u computed by the algorithm. The algorithm also uses a first-in, first-out queue Q (see Section 10.1) to manage the set of gray vertices. 
 

Figure 22.3 illustrates the progress of BFS on a sample graph. 
 
Figure 22.3 The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of u.d appears within each vertex u. The queue Q is shown at the beginning of each iteration of the while loop of lines 10–18. Vertex distances appear below vertices in the queue. 

The results of breadth-first search may depend upon the order in which the neighbors of a given vertex are visited in line 12: the breadth-first tree may vary, but the distances d computed by the algorithm will not. 

Analysis: 
Before proving the various properties of breadth-first search, we take on the some-what easier job of analyzing its running time on an input graph G=(V, E). We use aggregate analysis, as we saw in Section 17.1. After initialization, breadth-first search never whitens a vertex, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, and so the total time devoted to queue operations is O(V). Because the procedure scans the adjacency list of each vertex only when the vertex is dequeued, it scans each adjacency list at most once. Since the sum of the lengths of all the adjacency lists is θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of the BFS procedure is O(V+E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G. 

Shortest paths: 
At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G=(V, E) from a given source vertex s ∈ V . Define the shortest-path distance δ(s,v) from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s,v)=∞ . We call a path of length δ(s,v) from s to v a shortest path from s to v. 有關於 BFS 能找出由 vertex s 到 graph G 的其他每一個 vertex 的證明可以參考書上 (Introduction to Algorithms) 598 頁的地方, 但很直覺的從上面的 algorithm 來看, 當你把 vertex s 從 queue Q 拿出來時, 你便知道了該點所有的臨點與該點距離差一 (v.d = u.d + 1) 並接著把這些未曾發現的點 (color=White) 加入到 queue 中, 如此當你從 queue 依序拿出 Vertex 時一定會按照從最接近 Vertex s 的點取出. 因此從取出點再走到其他未被發現的點一定保證會是從 vertex s 走到該點的最近距離! 如此可知道從 BFS algorithm 可以計算出來從 source vertex s 走到 graph 其它 vertex 的最近距離.

Java Implementation:
底下是針對上面介紹的 BFS 使用 Java 進行 algorithm 的實作, 首先需要準備一些會使用到的類別:
- enum EColor: 標示 Vertex 的顏色

view plaincopy to clipboardprint?

1. package intralg.ch22;  
2.   
3. public enum EColor {      
4.     White("White"),Gray("Gray"),Black("Black");  
5.     private String msg;  
6.     private EColor(String msg){this.msg = msg;}  
7.     @Override  
8.     public String toString(){return msg;}  
9. }  

- class Vertex: 代表 Graph 中的 Vertex, 從屬性 adjacent_list 可以知道該點的鄰近點.

view plaincopy to clipboardprint?

1. package intralg.ch22;  
2.   
3. import java.util.LinkedList;  
4. import java.util.List;  
5.   
6. public class Vertex {  
7.       
8.     public Vertex(E data){this.data = data;adjacent_list=new LinkedList>();}  
9.     public E data; // data  
10.     public int d=Integer.MAX_VALUE; // distance  
11.     public EColor color=EColor.White; // White/Gray/Black  
12.     public Vertex pi; // parent, predecessor  
13.     public List> adjacent_list; // adjacency list  
14.     public void addNeighborVtx(Vertex ...vs)  
15.     {  
16.         for(Vertex v:vs) adjacent_list.add(v);  
17.     }  
18.       
19.     @Override  
20.     public String toString()  
21.     {  
22.         return String.format("{data:%s,distance:%d,color:%s,pi:%s}", data, d, color, pi!=null?pi.data:"NIL");  
23.     }  
24. }  

- class GAlg: 在這個類別我們定義一些常用的 Graph algorithms, 這邊會用到的是 BFS

view plaincopy to clipboardprint?

1. package intralg.ch22;  
2.   
3. import java.util.ArrayList;  
4. import java.util.LinkedList;  
5. import java.util.List;  
6. import java.util.Queue;  
7.   
8. public class GAlg {  
9.     @SuppressWarnings("unchecked")  
10.     public static List> GenBFSData()  
11.     {  
12.         List> vertex_list = new ArrayList>();  
13.         Vertex s = new Vertex('s'); vertex_list.add(s);  
14.         Vertex w = new Vertex('w'); vertex_list.add(w);  
15.         Vertex r = new Vertex('r'); vertex_list.add(r);         
16.         Vertex t = new Vertex('t'); vertex_list.add(t);  
17.         Vertex u = new Vertex('u'); vertex_list.add(u);  
18.         Vertex v = new Vertex('v'); vertex_list.add(v);         
19.         Vertex x = new Vertex('x'); vertex_list.add(x);  
20.         Vertex y = new Vertex('y'); vertex_list.add(y);  
21.         r.addNeighborVtx(s,v);  
22.         s.addNeighborVtx(w,r);  
23.         t.addNeighborVtx(w,x,u);  
24.         u.addNeighborVtx(t,x,y);  
25.         v.addNeighborVtx(r);  
26.         w.addNeighborVtx(s,t,x);  
27.         x.addNeighborVtx(w,t,u,y);  
28.         y.addNeighborVtx(x,u);  
29.         return vertex_list;  
30.     }  
31.       
32.     public static void BFS(List> graph)  
33.     {  
34.         Queue> queue = new LinkedList>();  
35.         Vertex s = graph.get(0);  
36.         s.color=EColor.Gray;  
37.         s.d = 0;  
38.         s.pi = null;  
39.         queue.add(s); // Initialize to make source vertex as first vertex from graph.         
40.         while(!queue.isEmpty()) // while Q!={};  
41.         {  
42.             Vertex u = queue.poll();  
43.             for(Vertex v:u.adjacent_list)  
44.             {  
45.                 if(v.color.equals(EColor.White))  
46.                 {                     
47.                     v.color = EColor.Gray;  
48.                     v.d = u.d+1;  
49.                     v.pi = u;  
50.                     queue.add(v);  
51.                     System.out.printf("\t\tDiscover %s by %s...\n", v, u.data);  
52.                 }  
53.             }  
54.             u.color = EColor.Black;  
55.             graph.remove(u);  
56.             System.out.printf("\t[Info] Vertex=%s is visited!\n", u);  
57.         }  
58.         if(graph.size()>0)  
59.         {  
60.             System.out.printf("\t[Info] Still some vertex not be visited:\n");  
61.             for(Vertex v:graph) System.out.printf("\t%s\n", v);  
62.         }  
63.         else  
64.         {  
65.             System.out.printf("\t[Info] All vertex of graph have been visited!\n");  
66.         }             
67.     }  
68.       
69.     public static void main(String args[])  
70.     {  
71.         List> graph = GenBFSData();  
72.         BFS(graph);  
73.     }  
74. }  

透過方法 GenBFSData() 我們產生書上範例的 Graph, 並呼叫方法 BFS() 進行 Breadth-first search, 執行結果如下:

Discover {data:w,distance:1,color:Gray,pi:s} by s...
Discover {data:r,distance:1,color:Gray,pi:s} by s...
[Info] Vertex={data:s,distance:0,color:Black,pi:NIL} is visited!
Discover {data:t,distance:2,color:Gray,pi:w} by w...
Discover {data:x,distance:2,color:Gray,pi:w} by w...
[Info] Vertex={data:w,distance:1,color:Black,pi:s} is visited!
Discover {data:v,distance:2,color:Gray,pi:r} by r...
[Info] Vertex={data:r,distance:1,color:Black,pi:s} is visited!
Discover {data:u,distance:3,color:Gray,pi:t} by t...
[Info] Vertex={data:t,distance:2,color:Black,pi:w} is visited!
Discover {data:y,distance:3,color:Gray,pi:x} by x...
[Info] Vertex={data:x,distance:2,color:Black,pi:w} is visited!
[Info] Vertex={data:v,distance:2,color:Black,pi:r} is visited!
[Info] Vertex={data:u,distance:3,color:Black,pi:t} is visited!
[Info] Vertex={data:y,distance:3,color:Black,pi:x} is visited!
[Info] All vertex of graph have been visited!