Breadth First Search

Slide 1:

Dept Futures Studies 2010-11 GRAPH SEARCH ALGORITHMS 1

Slide 2:

Dept Futures Studies 2010-11 Graph Search Algorithms Systematic search of every edge and every vertex of a graph. Graph G=(V,E) is either directed or undirected . Applications Compilers Networks Routing, Searching, Clustering, etc. 2

Slide 3:

Dept Futures Studies 2010-11 Graph Traversal Breadth First Search (BFS ) Start several paths at a time, and advance in each one step at a time Depth First Search (DFS ) Once a possible path is found, continue the search until the end of the path 3

Slide 4:

Dept Futures Studies 2010-11 4 Breadth-first search starts at a given vertex s , which is at level 0. In the first stage, we visit all the vertices that are at the distance of one edge away. When we visit there, we paint as " visited ," the vertices adjacent to the start vertex s - these vertices are placed into level 1. In the second stage, we visit all the new vertices we can reach at the distance of two edges away from the source vertex s. These new vertices, which are adjacent to level 1 vertices and not previously assigned to a level, are placed into level 2, and so on. The BFS traversal terminates when every vertex has been visited. Breadth-First Search

Breadth-First Search:

Dept Futures Studies 2010-11 Breadth-First Search The algorithm maintains a queue Q to manage the set of vertices and starts with s, the source vertex Initially, all vertices except s are colored white, and s is gray. BFS algorithm maintains the following information for each vertex u: - color[u] (white, gray, or black) : indicates status white = not discovered yet gray = discovered, but not finished black = finished - d[u] : distance from s to u - π[u] : predecessor of u in BF tree 5

Slide 6:

Dept Futures Studies 2010-11 Each vertex is assigned a color. In general, a vertex is white before we start processing it, it is gray during the period the vertex is being processed, and it is black after the processing of the vertex is completed. 6

Slide 7:

Dept Futures Studies 2010-11 BFS Algorithm Inputs: Inputs are a graph(directed or undirected) G =(V, E) and a source vertex s, where s is an element of V. The adjacency list representation of a graph is used in this analysis. 7

Slide 8:

Dept Futures Studies 2010-11 Outputs: The outputs are a predecessor graph, which represents the paths travelled in the BFS traversal, and a collection of distances, which represent the distance of each of the vertices from the source vertex. 8

Slide 9:

Dept Futures Studies 2010-11 9 1. for each u in V − { s } 2. do color[ u ] ← WHITE 3.                 d[ u ] ← infinity 4. π[ u ] ← NIL 5.         color[ s ] ← GRAY 6.         d[ s ] ← 0 7. π[ s ] ← NIL 8.         Q ← {} 9.         ENQUEUE(Q, s ) 10 while Q is non-empty 11. do u ← DEQUEUE(Q) 12. for each v adjacent to u 13. do if color[ v ] ← WHITE 14. then color[ v ] ← GRAY 15.                                          d[ v ] ← d[ u ] + 1 16. π[ v ] ← u 17.                                          ENQUEUE(Q, v ) 18.                 DEQUEUE(Q) 19.         color[ u ] ← BLACK BFS Algorithm

Slide 10:

Dept Futures Studies 2010-11 1 . Enqueue (Q,s) 2. while Q ≠  3. do u  Dequeue (Q) 4. for each v adjacent to u 5. do if color[v] = white 6. then color[v]  gray 7. d[v]  d[u] + 1 8.  [v]  u 9. Enqueue ( Q,v ) 10. color[u]  black Note : If G is not connected, then BFS will not visit the entire graph (without some extra provisions in the algorithm) 10

Slide 11:

Dept Futures Studies 2010-11 r v w x y u t s Graph G=(V, E) 11

Slide 12:

Dept Futures Studies 2010-11 S r u t s v w x y 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ Q 0 r u t s v w x y 0 1 ∞ ∞ ∞ ∞ 1 ∞ Q 1 1 w r 12

Slide 13:

Dept Futures Studies 2010-11 r t x r u t s v w x y 0 1 ∞ ∞ 2 ∞ Q 1 2 2 2 1 t x v Q 1 2 2 r u t s v w x y 0 1 ∞ ∞ 2 2 1 1 2 13

Slide 14:

Dept Futures Studies 2010-11 x v u r u t s v w x y 0 3 ∞ 2 Q 2 2 3 2 1 1 2 r u t s v w x y 0 3 3 2 Q 2 3 3 2 1 1 2 v u y 14

Slide 15:

Dept Futures Studies 2010-11 r u t s v w x y 0 3 3 2 Q 3 3 2 1 1 2 u y r u t s v w x y 0 3 3 2 Q 3 2 1 1 2 y 3 15

Slide 16:

Dept Futures Studies 2010-11 3 Q r u t s v w x y 0 3 2 2 1 1 2 3 Empty r u t s v w x y 0 3 2 2 1 1 2 3 Spanning Tree 16

Slide 17:

Dept Futures Studies 2010-11 BFS (G, s) 0. For all i ≠ s, d[ i ]=∞; d[s]=0 1. Enqueue (Q,s) 2. while Q ≠  3. do u  Dequeue (Q) 4. for each v adjacent to u 5. do if color[v] = white 6. then color[v]  gray 7. d[v]  d[u] + 1 8.  [v]  u 9. Enqueue ( Q,v ) 10. color[u]  black each node enqueued and dequeued once = O(V) time each edge considered once (in each direction) = O(E) time Complexity Running Time of BFS 17

Slide 18:

Dept Futures Studies 2010-11 18 Running Time of BFS We will denote the running time by T(m, n) where m is the number of edges and n is the number of vertices. Let V ′ subset of V be the set of vertices enqueued on Q. Then, T(m, n) = O(m+ n)

Analysis of Breadth-First Search:

Dept Futures Studies 2010-11 Analysis of Breadth-First Search Shortest-path distance  ( s,v ) : minimum number of edges in any path from vertex s to v. If no path exists from s to v, then  ( s,v ) = ∞ The ultimate goal of the proof of correctness is to show that d[v] =  ( s,v ) when the algorithm is done and that a path is found from s to all reachable vertices. 19

Analysis of Breadth-First Search:

Dept Futures Studies 2010-11 Analysis of Breadth-First Search Lemma 1 : Let G = (V, E) be a directed or undirected graph, and let s be an arbitrary vertex in G. Then for any edge (u, v)  E,  ( s,v )   ( s,u ) + 1 Case 1 : If u is reachable from s, then so is v. In this case, the shortest path from s to v can't be longer than the shortest path from s to u followed by the edge ( u,v ). Case 2 : If u is not reachable from s, then  ( s,u ) = ∞ In either case, the lemma holds. 20

Slide 21:

Dept Futures Studies 2010-11 Show that d[v] =  ( s,v ) for every vertex v. Lemma 2 : Let G = (V, E) be a graph, and suppose that BFS is run from vertex s. Then for each vertex v, the value d[v] ≥  ( s,v ). By induction on the number of enqueues (line 9). Basis : When s is enqueued , d[s] = 0 =  ( s,s ) and d[v] = ∞ ≥  ( s,v ) for all other nodes. Ind.Step : Consider a white vertex v discovered from vertex u. implies that d[u] ≥  ( s,u ). Then d[v] = d[u] + 1 ≥  ( s,u ) + 1 ≥  ( s,v ). Therefore, d[v] bounds  ( s,v ) from above. 21

Slide 22:

Dept Futures Studies 2010-11 Lemma 3 : For every vertex (v 1 ,v 2 ,..., v r ) on Q during BFS (such that v 1 is Q head and v r is Q rear), d[ v r ] ≤ d[v 1 ] + 1 and d[v i ] ≤ d[v i+1 ] for i = 1,2,..., r-1. By induction on the number of queue operations. Basis : Q contains only s, so lemma trivially holds. Ind.Step : Case 1 : Show lemma holds after every dequeue . Suppose v 1 is dequeued and v 2 becomes new head. Then d[v 1 ] ≤ d[v 2 ] d[ v r ] ≤ d[v 1 ] + 1 ≤ d[v 2 ] + 1, so lemma holds after every dequeue . 22

Slide 23:

Dept Futures Studies 2010-11 Lemma 3: For every vertex (v 1 ,v 2 ,..., v r ) on Q during BFS (such that v 1 is Q head and v r is Q rear), d[ v r ] ≤ d[v 1 ] + 1 and d[v i ] ≤ d[v i+1 ] for i = 1,2,..., r-1 Case 2 : Show lemma holds after every enqueue . Suppose v is enqueued , becoming v r+1 after vertex u is dequeued (i.e., v is adjacent to u). Then for the new head v 1 d[u] ≤ d[v 1 ] d[ v r ] ≤ d[u] + 1 = d[v] = d[v r+1 ] So after the enqueue , we have that d[ v r ] = d[v] = d[u] + 1 ≤ d[v 1 ] + 1. Also, d[ v r ] ≤ d[v r+1 ] and for all other nodes on Q, d[v i ] ≤ d[v i+1 ] . As a consequence of Lemma 3 , if v i is enqueued before v j , then d[v i ] ≤ d[ v j ] (also, if v i is enqueued before v j , then it is also dequeued before v j by definition of a queue). 23

Slide 24:

Dept Futures Studies 2010-11 Theorem 4 : (Correctness of BFS ) Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run from a given source vertex s  V. Then, during execution, BFS discovers every vertex v ≠ s that is reachable from the source s, and upon termination, d[v] =  ( s,v ) for every reachable or unreachable vertex v. Proof by contradiction. Assume that for some vertex v that d[v]   ( s,v ). Also, assume that v is the vertex with minimum  ( s,v ) that receives an incorrect d value. By Lemma 2 , it must be that d[v] >  ( s,v ). 24

Slide 25:

Dept Futures Studies 2010-11 25 Case 1 : v is not reachable from s. Then  ( s,v ) = ∞ = d[v]. This is a contradiction, and the Thm holds. Case 2 : v is reachable from s. Let u be the vertex immediately preceding v on a shortest path from s to v, so that  ( s,v ) =  ( s,u ) + 1. Because  ( s,u ) <  ( s,v ) and because v is the vertex with the minimum  ( s,v ) that receives an incorrect d value, d[u] =  ( s,u ). So we have d[v] >  ( s,v ) =  ( s,u ) + 1 = d[u] + 1 (by L.1 and how we chose v as minimum  ( s,v ) that receives an incorrect d value).

Slide 26:

Dept Futures Studies 2010-11 Consider the time t when u is dequeued . At time t, v is either white, gray, or black. We can derive a contradiction in each of these cases. Case 1 : v is white. Then in line 7, d[v] = d[u]+1. Case 2 : v is black. Then v was already dequeued , and therefore d[v] ≤ d[u] (by L. 3 ). Case 3 : v is gray. Then v turned gray when it was visited from some vertex w, which was dequeued before u. Then d[v] = d[w] + 1. Since d[w] ≤ d[u] (by L 3 ), d[v] ≤ d[u] + 1. Each of these cases is a contradiction to d[v] >  ( s,v ), so we conclude that d[v] =  ( s,v ). 26

Slide 27:

Dept Futures Studies 2010-11 27 Applications of BFS Connected components Bipartite

Slide 28:

Dept Futures Studies 2010-11 28 Find the number of connected components of a graph. Describe with diagram.

Slide 29:

Dept Futures Studies 2010-11 29 Bipartite Graph A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V 1 and V 2 such that ( u , v ) E implies either u in V 1 and v in V 2 or u in V 2 and v in V 1 . That is, all edges go between the two sets V 1 and V 2 .

Slide 30:

Dept Futures Studies 2010-11 30 whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray' our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[ u ] and d[ v ] have the same parity, then the graph is not bipartite.

Slide 31:

Dept Futures Studies 2010-11 31 Level 0 Level 3 Level 1 Level 2 a c i d h e b f g j Queue E f g 2 2 3 Odd cycle

Slide 32:

Dept Futures Studies 2010-11 32 Thank You Jyothimon C Dept Futures Studies University of KERALA jyothimon86@gmail.com