## 2013年4月8日 星期一

### [ Intro Alg ] Elementary Graph Algorithms - Breadth-ﬁrst search

Preface:
Breadth-ﬁrst 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-ﬁrst search.

Given a graph G=(V,E) and a distinguished source vertex s, breadth-ﬁrst 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-ﬁrst tree” with root s that contains all reachable vertices. For any vertex reachable from s, the simple path in the breadth-ﬁrst 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-ﬁrst 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 ﬁrst time it is encountered during the search, at which time it becomes nonwhite. Gray and black vertices, therefore, have been discovered, but breadth-ﬁrst search distinguishes between them to ensure that the search proceeds in a breadth-ﬁrst 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-ﬁrst search constructs a breadth-ﬁrst 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-ﬁrst tree. Since a vertex is discovered at most once, it has at most one parent. Ancestor and descendant relationships in the breadth-ﬁrst tree are deﬁned 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-ﬁrst-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 ﬁrst-in, ﬁrst-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-ﬁrst search may depend upon the order in which the neighbors of a given vertex are visited in line 12: the breadth-ﬁrst tree may vary, but the distances d computed by the algorithm will not.

Analysis:
Before proving the various properties of breadth-ﬁrst 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-ﬁrst 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-ﬁrst 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-ﬁrst search ﬁnds the distance to each reachable vertex in a graph G=(V, E) from a given source vertex s ∈ V . Deﬁne 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:

- enum EColor: 標示 Vertex 的顏色
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 可以知道該點的鄰近點.
1. package intralg.ch22;
2.
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.     {
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
1. package intralg.ch22;
2.
3. import java.util.ArrayList;
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);
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();
44.             {
45.                 if(v.color.equals(EColor.White))
46.                 {
47.                     v.color = EColor.Gray;
48.                     v.d = u.d+1;
49.                     v.pi = u;
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. }

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!

### [ Py DS ] Ch5 - Machine Learning (Part2)

Source From  Here   Introducing Scikit-Learn   There are several Python libraries that provide solid implementations of a range of machin... 