图形G是由两个集合V和E所构成的.ppt

1、Graph Algorithms,圖形G是由兩個集合V和E所構成的，可以寫成G=(V,E)。其中V是非空的由有限個頂點(Vertex)所構成的集合，E則是由頂點對所構成的集合，這些頂點對叫做邊(edge)。V(G)和E(G)各表示組成G的頂點集合和邊集合。依據E中邊之型態，所組成之圖形又可分成下列兩種： E中之邊沒有方向性，亦即（1,2）和（2,1）表示相同的邊，如此構成之圖形稱作無向圖形（undirected graph）。 E之邊沒有方向性，頂點對（邊）以1,2表示，其中表頭（head），1表尾（tail）；很自然地，2,1和，1,2是完全不同的兩個邊。以此種邊集合構成之圖形稱作有向圖形（

2、directed graph，又稱digraph）。,complete graph：各種頂點的組合均存在之圖形稱作complete graph。無向圖形若有n個頂點，則最大可能之邊組合有（）種，而有向圖形將有兩倍於此為n(n-1)種組合；含有n個頂點之complete graph將有如上數目之邊。 subgraph：若為之subgraph，則為一graph，且()V(V)，E(G)E(G)。 path：由圖形中頂點所構成的序列p,1,2,N,q，若其中(p,1), (1,2),，(N,q)均為圖形中之邊，則此序列稱做一path；一path中edge之數目稱做該path之長度；在有向圖形之情況下

3、，則要求p,1, 1,2,，N,q均為有向edge，而此path又稱做directed path。 Simple path：在上面之定義中，其除了p和q之外，其他vertex均不重複出現的path稱之。在simple path中，若p=q，則稱之為cycle或circuit。一graph若有cycle則稱cyclic，反之則可稱做acyclic。 一path若不為simple，則其必有相交之情況。,頂點和邊之關係,以“adjacent”和“incident”描述之：,1和2為adjacent 1 adjacent from2 1 incident on1(2) 2 adjacent to1 2

4、 incident to1(2),相連（Connected） connected of two vertices：若一圖形中之兩頂點間存在任何path，則稱他們為connected的。在有向圖形中，若兩點頂間存在自其中某頂點到另一頂點和回來之有向path，則稱此兩頂點為strongly connected。 connected of a graph：若一圖形其所有頂點對均為6 connected，則此graph為connected：相似地，若一有向圖形所有頂點對間均為strongly connected，該圖形亦為strongly connected。 degree (of a vertex)

5、：表示一個vertex所adjacent之其他vertices之個數。在有向圖形中，degree又分成in-degree和out-degree，其中前者表示該vertex所adjacent from之vertex個數，而後者表示所adjacent to之vertex個數。,connected component：對無向圖形而言，其connected component（或component）表示其孤立的connected的子圖，這可能有好幾個。在有向圖形中，strongly connected component表示一盡量伸展而仍然保持strongly connected 的子圖（不一定要孤立

6、）。以下四個圖形G1到G4前三個均只有一個component（G3沒有strongly connected component），而G4有兩個component。,路徑長度為n之鄰接矩陣,在找出路徑矩陣p時，首先要找到a2 ，然後a3，一直到an，最後再將a1，a2，an加起來得到Sn，再由Sn得到p。,Warshalls algorithm: 1. pa（把鄰接矩陣a拷貝至p） 2. for（k=1；k=n；k+） for（i=1；i=n；i+） for（j=1；j=n；j+） pij=pij | pik&pkj；,Warshalls algorithm,Representations of

7、 graphs：undirected graph An undirected graph G have five vertices and seven edges An adjacency-list representation of G The adjacency-matrix representation of G,vertex,edge,1,2,2,5,/,1,3,2,4,/,4,2,5,4,1,2,3,4,5,1,2,3,4,5,0,1,0,0,1,1,0,1,1,1,0,1,0,1,0,0,1,1,0,1,1,1,0,0,0,5,3,4,/,5,3,/,1,1,/,Represent

8、ations of graphs：directed graph An directed graph G have six vertices and eight edges An adjacency-list representation of G The adjacency-matrix representation of G,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,0,1,0,1,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,6,6,0,0,0,0,0,6,0,0,1,0,0,1,The operation of BFS on an

9、undirected graph,(a),0,t,v,w,r,s,y,u,x,s,0,Q,(b),0,t,v,w,r,s,y,u,x,w,1,Q,1,1,r,1,(c),0,t,v,w,r,s,y,u,x,r,1,Q,1,1,t,2,2,2,x,(d),0,t,v,w,r,s,y,u,x,t,1,Q,1,1,x,2,2,2,v,2,2,2,(e),0,t,v,w,r,s,y,u,x,x,2,Q,1,1,v,2,2,2,u,2,3,3,(f),0,t,v,w,r,s,y,u,x,v,2,Q,1,1,u,3,2,2,y,2,3,3,3,(g),0,t,v,w,r,s,y,u,x,u,3,Q,1,1

10、,y,3,2,2,2,3,(h),0,t,v,w,r,s,y,u,x,y,3,1,1,2,2,2,3,3,3,(i),0,t,v,w,r,s,y,u,x,Q,1,1,2,2,2,3,3,Breadth-first search： Initially, vertices are colored white. Discovered vertices are colored green. When done, discovered vertices are colored black. du stores the distance from s to u. is a predecessor to u

11、 on its shortest path. Q is a first-in first-out queue.,Algorithm： Complexity：,BFS(G,s),for each vertex u in VG s,do coloru - white,1.,2.,du - infinity,3.,piu - NIL,4.,colors - gray,5.,ds - 0,6.,pis - NIL,7.,Q - s,8.,While Q .ne. ,9.,do u - headQ,10.,for each v in Adju,11.,do if colorv = white,12.,t

12、hen colorv - gray,13.,dv - du+1,14.,Piv - u,15.,Enqueue(Q,v),16.,Dequeue(Q),17.,coloru - black,18.,Properties of Breadth-first search： After execution of BFS, all nodes reachable from the source s are colored black. After execution of BFS, dv is the distance of a shortest path from the source s to v

13、 for vertices v reachable from s. After execution of BFS, if v is reachable from s, then one of the shortest paths to v passes through the edge ( ) at the end. After execution of BFS, the edges( ) for v reachable from s from a breadth-first tree.,Lemma1： G=(V,E)：a directed or undirected graph. s：an

14、arbitrary vertex ： the shortest-path distance from s to v.,Then for any,Proof：,Lemma2： G=(V,E)：a directed or undirected graph. s：an arbitrary vertex ： the distance from s to u computed by the algorithm,Suppose that BFS is run on G from s.,Proof：,Then on termination, for each vertex , the value dv co

15、mputed by BFS satisfies,By induction on the number of times a vertex is placed in the queue Q.,Basis： when s is placed in Q.,for all,Induction Step： Consider a white vertex v discovered during the search from a vertex u.,Inductive hypothesis implies,By lemma1,From then on, dv wont be changed again.,

16、Lemma3： Q： the queue when BFS executes on a graph G=(V,E).,Then,Proof：,By induction on the number of queue operations.,Basis： when Q has only s.,Induction Step：,by inductive hypothesis.,head,tail,and,for i=1,2,r-1.,1： after dequeue：,v2 becomes the new head in Q.,2：after enqueue a new vertex v into t

17、he Q.,Let vr+1 be v.,Note that vis adjacency list is being scanned.,neighbors,Thus,And,The rest , for I=1,r-1, remain unaffected.,Thm： 1. During the execution of BFS on G=(V,E), BFS discovers every vertex that is reachable from s, and on termination 2. For any vertex reachable form s, one of the sho

18、rtest paths from s to v is the shortest path form s to followed by the edge,Proof：,If v unreachable from s,By induction on k, we want to prove for each there is exactly on point during The execution of BFS at which 1. V is grayed 2. Dv=k 3. if then 4. v is inserted into Q.,By BFS, v is never discove

19、red.,Let,Basis： k=0, Vk=s clear !,Induction Step：,until BFS terminates.,Once u is inserted into Q, du and never change.,By lemma 3,grayed,Let , then by lemma 2.,Thm：,The monotonicity property, with and the inductive hypothesis implies that v must be discovered after all vertices in Vk-1 are enqueued

20、, if v is discovered at all.,Since a path of k edges from s to v, such that,At some point u must be the head in Q. Then us neighbors are scanned and v is discovered.,Line 13 grays v, line 14 sets dv=du+1=k.,Line 15 sets,Line 15 enqueues v.,Thus, the inductive hypothesis holds.,If then,Thus, we can o

21、btain a shortest path from s to v by taking a shortest path from s to then traversing the edge,Depth-first search： Nodes are initially white Nodes become green when first discovered Nodes become black when they are done dv records when v is first discovered Fv records when v is done du fu,1/,(a),u,v

22、,w,x,y,z,1/,2/,(b),u,v,w,x,y,z,1/,2/,3/,(c),u,v,w,x,y,z,1/,2/,4/,3/,(d),u,v,w,x,y,z,Discovery time,1/,2/,4/,3/,(e),u,v,w,x,y,z,B,1/,2/,4/5,3/,(f),u,v,w,x,y,z,B,1/,2/,4/5,3/6,(g),u,v,w,x,y,z,B,1/,2/7,4/5,3/6,(h),u,v,w,x,y,z,B,1/,2/7,4/5,3/6,(i),u,v,w,x,y,z,B,F,1/8,2/7,4/5,3/6,(j),u,v,w,x,y,z,B,F,1/8,

23、2/7,9/,4/5,3/6,(k),u,v,w,x,y,z,B,F,1/8,2/7,9/,4/5,3/6,(l),u,v,w,x,y,z,B,F,C,1/8,2/7,9/,4/5,3/6,10/,(m),u,v,w,x,y,z,B,F,C,1/8,2/7,9/,4/5,3/6,10/,(n),u,v,w,x,y,z,B,F,C,B,1/8,2/7,9/,4/5,3/6,10/11,(o),u,v,w,x,y,z,B,F,C,B,1/8,2/7,9/12,4/5,3/6,10/11,(o),u,v,w,x,y,z,B,F,C,B,(u,v) Black edges: if u is conne

24、cted to an ancestor v in a depth- first tree. (eg self-loop) Forward edges: if u is connected to an descendant v in a depth-first tree. Cross edges: if u is not connected to an ancestor v in the same depth-first tree. OR if v is not connected to an ancestor u in the same depth-first tree. OR if u an

25、d v belong to different depth-first trees.,DFS(G) for each vertex u in VG do coloru white piu NIL time 0 for each vertex u in VG do if coloru = white then DFS-Visit(u),O(V),O(E),DFS-Visit(u) coloru gray du time time + 1 for each v in Adju do if colorv = white then piv u DFS-Visit(v) coloru black fu

26、time time + 1,Finishing time,Discovery time,The running time of DFS is O(V+E) After execution of DFS, all nodes are colored black After execution of DFS, the edges( ) form a collection of depth-first tree, called a depth-first forest.,Edge Classification 1. Tree edges( u, v ): u was discovered first

27、 using ( u,v ) 2. Back edges( u, v ): v is an ancestor of u in the DFS tree 3. Forward edges( u, v ): v is a descendent of u, not a tree edge 4. Cross edges( u, v ): Other edges Example In a depth-first search of an undirected graph, every edge is either a tree edge or a back edge,1 2 3 4 5 6 7 8 9

28、10 11 12 13 14 15 16,( s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t),s,z,y,w,x,t,v,u,(b),(c),s,z,y,x,w,v,u,t,B,B,C,C,C,C,F,Thm6: In any DFS of a graph G=( V,E ), for any two vertices u,v, exactly one of the following 3 conditions holds: (1). The intervals du, fu and du, fu are disjoint, (2). The in

29、terval du, fu is contained entirely within the interval dv, fv, and u is a descendant of v in the depth-first tree, (3). or as above with v as a descendant of u,Pf: 1. If du dv case 1: dv fu : So v is finished before finishing u. Thus (3) holds case 2: fu dv du fu dv fv (1) holds 2. If dv du: Simila

30、rly, by switching the roles of u and v,v was discovered while u was still gray.,v is a descendant of u, and all vs outgoing edges are explored,Cor7: v is a proper descendant of vertex u in the depth-first forest for a graph G iff du dv fv fu Thm8: In a DF forest of G=( V,E ), vertex v is a descendan

31、t of u iff at the time du that the search discovers u, v can be reached from u along a path consisting entirely of white vertices,Pf: “” v: descendant of u “” Assume at time du, v is reachable from u along a path of white vertices, but v does not become a descendant of u in DF tree Thus, du dv fw =

32、fu Thm6 implies dv, fv is contained entirely in du, fu By Cor7, v is a descendant of u.,du dw, by the above cor.,Thus w is white at du,fw = fu v must be discovered after u is discovered, but before w is finished.,Thm 9: In a DFS of an undirected graph G, every edge of G is either a tree edge or a ba

33、ck edge Pf: Let and suppose du dv. Then v must be discovered and finished before finishing u If (u, v) is explored first in the direction from u to v, then (u, v) becomes a tree edge If (u, v) is explored first in the direction from v to u, then (u, v) is a back edge, since u is still gray at the ti

34、me (u, v) is first explored,Topological sort 定義：A topological sort of a dag G=(V, E) is a linear ordering of all its vertices. (dag: Directed acyclic graph)如 edge(u, v), u appears before v in the ordering,TOPOLOGICAL-SORT(G): (V+E) 1. Call DFS(G) to compute finishing times fv for each vertex v (V+E)

35、 2. As each vertex is finished, insert it onto the front of a linked list O(1) 3. Return the linked list of vertices,Lemma 23.10 A directed graph G is acyclic iff DFS(G) yields no back edges. pf: Suppose there is a back edge (u,v), v is an ancestor of u. Thus there is a path from v to u and a cycle

36、exists. Suppose G has a cycle c. We show DFS(G) yields a back edge. Let v be the first vertex to be discovered in c, and (u,v) be the preceding edge in c. At time dv, there is a path of white vertices from v to u. By the white-path thm., u becomes a descendant of v in the DF forest. (u,v)is a back e

37、dge.,Thm 23.11 TOPOLOGICAL-SORT(G) produces a topological sort of G pf: Suppose DFS is run to determinate finishing times for vertices. It suffices to show that for any pair of u,v ,if there is an edge from u to v, then fvfu. When (u,v) is explored by DFS(G), v cannot be gray. Therefore v must be ei

38、ther white or black. 1. If v is white, it becomes a descendant of u, so fvfu 2. If v is black, then fvfu,Strongly connected components: A strongly connected component of a directed graph G(V,E) is a maximal set of vertices U V s.t. for every pair u, vU, u and v are reachable from each other. Given G

39、=(V,E), define GT=(V,ET), where ET=(u,v): (v,u)EGiven a G with adjacency-list representation, it takes O(V+E) to create GT. G and GT have the same strongly connected components.,StronglyConnectedComponents(G) 1. Call DFS(G) to compute finishing times fu for each vertex u 2. Compute GT 3. Call DFS(GT

40、), but in the main loop of DFS, consider the vertices in order of decreasing fu 4. Output the vertices of each tree in the depth-first forest of step 3 as a separate strongly connected component Time: (V+E),Lemma 12: If 2 vertices are in the same strongly connected component, then no path between th

41、em ever leaves the strongly connecter component. pf: Assume that: u, v in the same component w is a vertex on the path from u to v uw wvu u, w are in the same component,Thm 13 In any depth-first search, all vertices in the same strongly connected component are placed in the same depth-first tree pf:

42、 By lemma 12 and thm 8, every vertex in the strongly connected component becomes a descendant of r in the depth-first tree,r: the first discovered vertex in the component,(u): forefather of u the vertex w such that u w and fw is maximized fu f(u) (*) (u) )= (u), for any u,vV, u v implies f(v) f(u) w

43、: v ww: u w (1) u v w (2) u w Since u (u) f(u) f(u) By (*), we have f(u) f(u) Thus, f(u)= f(u) and (u)= (u), since only one vertex can be finished at a time.,w,w,Thm 14 In a directed graph G=(V,E), the forefather (u) of any vertex uV in any depth-first search of G is an ancestor of u. pf: (u)=u : tr

44、ivial, u is reachable from itself. (u) u : at time du, (u) can be (i) black (ii) gray (iii) white (i) If (u) is black, then f(u) f(u) Since (u) should have the maximum finishing time,u,(u),Last nonwhite vertex on this path,t,Corollary 15 In any DFS of a directed graph G, vertices u and (u), for all uV, lie in the same strongly connected component. pf: u (u), by definition. (u) u, some (u) is an ancestor of u, by Thm 14,Thm 16 G=(V,E): a directed graph u,vV lie in the same strongly connected component the