Lecture 2 Elementary Graph Algorithms,Breadth-First Search Algorithm And Depth-First Search Algorithm, 2005 SDU 2,Breadth-first search (outline),The single source shortest-paths problem for unweighted graph The Breadth-first search algorithm The running time of BFS algorithm The correctness proof Note: We only introduce BFS for undirected graphs. But it also works for directed graphs.,Archetype for Prims minimum-spanning-tree algorithm Archetype for Dijkstras shortest-paths algorithm, 2005 SDU 3,Shortest paths,Example: 3 simple paths from source s to b: , , of length 1, 2, 3, respectively. So the shortest path from s to b is . The shortest paths from s to other vertices a, e, d, c are: , , , . There are two shortest paths from s to d., 2005 SDU 4,The shortest-paths problem,Distance dv: The length of the shortest path from s to v. For example dc=2. Define ds=0. The problem: Input: A graph G = (V, E) and a source vertex sV Output: A shortest path from s to each vertex v V and the distance dv., 2005 SDU 5,What does the BFS do?,Given a graph G = (V, E), the BFS returns: The shortest distance dv from s to v The predecessor or parent v, which is used to derive a shortest path from s to vertex v.（ see back ） BFS actually returns a shortest path tree in which the unique simple path from s to node v is a shortest path from s to v in the original graph. In addition to the two arrays dv and v, BFS also uses another array colorv, which has three possible values: WHITE: represented “undiscovered” vertices; GRAY: represented “discovered” but not “processed” vertices; BLACK: represented “processed” vertices., 2005 SDU 6,The Breadth-First Search,The idea of the BFS: Each time, search as many vertices as possible. Visit the vertices as follows: Visit all vertices at distance 1 Visit all vertices at distance 2 Visit all vertices at distance 3 Initially, s is made GRAY, others are colored WHITE. When a gray vertex is processed, its color is changed to black, and the color of all white neighbors is changed to gray. Gray vertices are kept in a queue Q., 2005 SDU 7,The Breadth-First Search (more details),G is given by its adjacency-lists. Initialization: First Part: lines 1 4 Second Part: lines 5 - 9 Main Part: lines 10 18 Enqueue(Q, v): add a vertex v to the end of the queue Q Dequeue(Q): Extract the first vertex in the queue Q, 2005 SDU 8,Example of Breadth-First Search,Problem: given the undirected graph below and the source vertex s, find the distance dv from s to each vertex v V, and the predecessor v along a shortest path by the algorithm described earlier., 2005 SDU 9,Example(Continued),Initialization,b,s,d,c,a,f,e,Q = (put s into Q (discovered), mark s gray (unprocessed),0, 2005 SDU 10,Example(continued),While loop, first iteration Dequeue s from Q. Find Adjs= Mark b,e as “G” Update db, de, b, e Put b, e into Q Mark s as “B” Q=,b,s,d,c,a,f,e,0,1,1, 2005 SDU 11,Example(continued),While loop, second iteration Dequeque b from Q, find Adjb= Mark a, c, f as “G”, Update da, dc, df, a, c, f Put a, c, f into Q Mark b as “B” Q=,b,s,d,c,a,f,e,0,1,1,2,2,2, 2005 SDU 12,Example(continued),While loop, third iteration Dequeque e from Q, find Adje= Mark d as “G”, mark e as “B” Update dd, d, Put d into Q Q=, 2005 SDU 13,Example(continued),While loop, fourth iteration Dequeque a from Q, find Adja= mark a as “B” Q=,b,s,d,c,a,f,e,0,1,1,2,2,2,2, 2005 SDU 14,Example(continued),While loop, fifth iteration Dequeque c from Q, find Adjc= mark c as “B” Q=, 2005 SDU 15,Example(continued),While loop, sixth iteration Dequeque f from Q, find Adjf= mark f as “B” Q=, 2005 SDU 16,Example(continued),While loop, seventh iteration Dequeque d from Q, find Adjd= mark d as “B” Q is empty, 2005 SDU 17,Example(continued),While loop, eighth iteration Since Q is empty, stop, 2005 SDU 18,Example(continued),Question: How do you construct a shortest path from s to any vertex by using the following table?, 2005 SDU 19,The Answer, 2005 SDU 20,Analysis of the Breadth-First Search Algorithm,We assume that it takes one unit time to test the color of a vertex, or to update the color of a vertex, or to compute dv = du + 1, or to set v = u, or to enqueue, or to