Breadth-First Search of Graphs.ppt

1、Breadth-First Search of Graphs,Prepared by John Reif, Ph.D. Distinguished Professor of Computer Science Duke University,Analysis of Algorithms,Applications of Breadth-First Search of Graphs,Single Source Shortest PathGraph Matching,Reading on Breadth-First Search of Graphs,Reading Selection: CLR, Ch

2、apter 24,Breadth-First Search Algorithm Input,Breadth-First Search Algorithm,Breadth-First Search Algorithm Output,Edges in Breadth-First Search,All edges u,v E have level distance 1,Breadth-First Search Tree,Breadth First Search Tree T,3,2,4,1,6,8,7,LEVEL(0) =1,LEVEL(1)=2,3,4,5,LEVEL(2)=6,7,8,5,roo

3、t r,Single Source Shortest Paths Problem,problem: For each vertex v, determine D(v) = min length path from root r to v,Dijkstras Algorithm for Single Source Shortest Paths,Example Single Source Shortest Paths Problem,example,Example Execution of Dijkstras Algorithm,Proof of Dijkstras Algorithm,Use i

4、nduction hypothesis:,Proof of Dijkstras Algorithm (contd),Time Cost of Dijkstras Algorithm on a RAM Model,Time cost: per iterationSince there are |V| iterations,Total Time O( |V| (log |V| ) + |E|),Graph Matching,Graph G = (V,E) Graph Matching M is a subset of E if e1, e2 distinct edges in M Then the

5、y have no vertex in commonVertex v is matched if v is in an edge of M,example,Graph Matching Problem,Graph Matching Problem:Find a maximum size matchingSuppose:G = (V,E) has matching MGoal: find a larger matching,Augmenting Path in G given Graph Matching M,An augmenting path p = (e1, e2, , ek),Graph

6、 Matching (contd),Initial matching M in GAugmenting pathp = (5,2), (2,6), (6,4), (4,7), (7,3),Graph Matching (contd),New matching M = P M = (P M) (P M),Characterization of a Maximum Graph Matching via Lack of Augmented Path,TheoremM is maximum matching iff there is no augmenting pathrelative to M,Pr

7、oof of Characterization of Maximum Graph Matching (contd),Proof (1) If M is smaller matching and p is an augmenting path for M,then M P is a matching size |M|(2) If M, M are matchings with |M| |M|,Claim: M M contains an augmenting path for M.,Proof The graph G = (V, M M )has only paths with edges al

8、ternating between M and M.Repeatedly delete a cycle in G (with equal number of edges in M, M )Since |M| |M| must eventually getaugmenting path remaining for M.,Maximum Matching Algorithm,Algorithm,Maximum Matching (contd),Remaining problem:Find augmenting pathAssume weighting d: E R+ = pos. reals,Ma

9、ximum Weighted Matching Algorithm,Assume weighting d: E R+ = positive reals Theorem Let M be maximum weight among matchings of size |M|. Let P be an augmenting path for M of maximum weight. Then matching M P is of maximum weight among matchings of size |M|+1.,Proof of Maximum Weighted Matching Algor

10、ithm,Proof Let M be any maximum weight matching of size |M|+ 1. Consider the graph G = (V, M M ). Then the maximum weight augmenting path p in G gives a matching M P of the same weight as M.,Bipartite Graph,Bipartite Graph G = (V,E),Breadth-First Search Algorithm for Augmented Path,Assume G is bipar

11、tite graph with matching M. Use Breadth-First Search:LEVEL(0) = some unmatched vertex r for odd L 0,LEVEL(L) = u|v,u E Mwhen v LEVEL(L -1)and when u in no lower level For even L 0,LEVEL(L) = u|v,u Mwhen vLEVEL(L -1)and u in no lower level,Proof of Breadth-First Search Algorithm for Augmented Path,Ca

12、ses(1) If for some odd L 0,LEVEL(L) contains an unmatched vertex uthen the Breadth First Search tree T has an augmenting path from r to u(2) Otherwise no augmenting path exists, soM is maximal.,Finding a Maximal Matching in a Bipartite Graph,Theorem If G = (V,E) is a bipartite graph, Then the maximu

13、m matching can be constructed in O(|V|(|V|+|E|) ) time.Proof Each stage requires O(|V|+|E|) time for Breadth First Search construction of augmenting path.,Generalizations of Matching Algorithm,Generalizations:,Computing Augmented Paths in General Graphs,Let M be matching in general graph G Fix start

14、ing vertex r to be an unmatched vertex,Why Algorithm for Augmented Paths in Bipartite Graphs does not work for General Graphs,Edmonds Algorithm for Augmented Paths in General Graphs,Blossom Shrinking Maintains the Existence of Augmented Paths,Theorem If G is formed from G by shrinking of blossom B,

15、thenG contains an augmenting path iff G does.,Proof of Blossom Shrinking,Proof (1) If G contains an augmenting path p,then if p visits blossom B we can insert anaugmenting subpath p within blossom intop to get a new augmenting path for G (2) If G contains an augmenting path, thenapply Edmonds blosso

16、m shrinking algorithmto find an augmenting path in G.,Edmonds Blossom Shrinking Algorithm,Main Ideas of Edmonds algorithm: The algorithm incrementally constructs a forest of trees whose paths are partial augmenting paths. If a cycle is formed, contract it to a vertex. Try to link two partial augment

17、ing paths of distinct trees to form a full augmenting path.,Edmonds Blossom Shrinking Algorithm (contd),Note: We will let P(v) = parent of vertex v,Main Loop,Edmonds Main Loop:,Main Loop (contd),Case 1 if w is “odd” then do nothing. Case 2 if w is “unreached” and matchedthen set w “odd” and set mate

18、 (w)“even”Set P(w) v , P(mate (w) w,Main Loop (contd),Case 3 if w is “even” and v, w are in distincttrees T, T then output augmentingpath p from root of T to v, through v,w, in T to root.,Main Loop (contd),Case 4 w is “even” and v,w in same tree Tthen v,w forms a blossom Bcontaining all vertices whi

19、ch areboth (i) a descendant of LCA(v,w) and (ii) an ancestor of v or wwhere LCA(v,w) = least common ancestor of v,w in T,Main Loop (contd),Shrink all vertices of B to a singlevertex b. Define p(b) = p(LCA(v,w)and p(x) = b for all x B,Proof Edmonds blossom-shrinking algorithm succeeds,LemmaEdmonds bl

20、ossom-shrinking algorithm succeeds iffProofUses an induction on blossom shrinking stages,Time Bounds for Matching in General Graphs,Edmonds blossom-shrinking algorithm costs time O(n4) Gabow and Tarjan implement in time O(nm) all O(n) stages of matching algorithmtaking O(m) time per stage for blossom shrinkingMicali and Vazirani using network flow to find augmented paths and reduce time to O(n1/2 m) for unweighted matching in general graphs,Breadth-First Search of Graphs,Prepared by John Reif, Ph.D. Distinguished Professor of Computer Science Duke University,Analysis of Algorithms,