内容提要 第七讲图的基本算法 CRepresentation of graphics E Breadth-first search EDepth-first search 2. Strongly connected components 图的应用背景 Representation of graphs z可以利用图描述的经典问题有 DEfinition of a graph Petri-Net NG=(, E) where V is a set of vertices, E is WOrk Flow another set call Edges is a sub set of ((u, v):u y城市与连接城市的道路 and v is element of VI 隔离区域间的分界线 2. Concepts of graphs 人与人之间的认识关系 DEnse graph: if El is close to V2. 系都可以用图来表示 sParse graph: If it is not dense 基本算法的应用 e。 gure 22.1 Two representations of an undirected graph on of G
1 清华大学 宋斌恒 1 第七讲 图的基本算法 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 Representation of graphics Breadth-first search Depth-first search Topological sort Strongly connected components 清华大学 宋斌恒 3 图的应用背景 可以利用图描述的经典问题有 Petri－Net Work Flow 城市与连接城市的道路 区域与隔离区域间的分界线 人与人之间的认识关系 任何二元关系都可以用图来表示 基本算法的应用 许多与图有关的算法需要做一种搜索 清华大学 宋斌恒 4 Representation of graphs Representation of graphs Definition of a graph: G = (V, E) where V is a set of vertices, E is another set call Edges is a sub set of {(u,v): u and v is element of V} Concepts of graphs: Dense graph: if |E| is close to |V|2. Sparse graph: If it is not dense 清华大学 宋斌恒 5 1 2 5 4 3 2 1 2 2 4 5 5 4 5 1 / / 3 3 2 / / 4 / 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 Figure 22.1 Two representations of an undirected graph. (a) An undirected graph G having five vertices and seven edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G. 清华大学 宋斌恒 6 1 2 5 4 3 2 5 / 6 2 / 4 / 5 / / 4 / 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 6
Adjacency-list representation Data structure of Adjacency-lis representation CLet G be a graph, for any u E V,we CA set of vertex objects denote Adju]=(v: (u,v)e E), call the list Vertex object contains one vertex u, and a of all adjacency vertices of u set of vertices Adjlu, which contains all its a:In general element in Adjlu] is unordered adjacency vertices of u E In an undirected graph 8? Using what data structure to represent a But in a directed graph set for the vertex objects Using what data structure to represent a Weighted Graph Adjacency-list representation for Weighted graphic s-We can assign value to the edges of a ErWe reconstruct the set Adju as graph, then we call such a graph is a aAdj[u={(,r):∈V,r∈R} where R is the weighted graph pace of real number or generally any object p Classically, a weighted graph has its edge space value belong to R, but we can extend it to values from any particular spaces, say, spaces containing complex obiects SHW: E R is the weight function More general graphics Matrix representation s-We can also assign values to the vertices A=(a) of a grap then it needs a more general Frau=1 if( D) EE, 0 else representation to present such a graph c-It is called the adjacency matrix s-IGive an Adjacency-list like data structure to represent such a graph 2?How to present it for the case of weighted E:?For more general case: there are information both on the vertices and edges?
2 清华大学 宋斌恒 7 Adjacency Adjacency-list representation list representation Let G be a graph, for any u ∈ V, we denote Adj[u] = { v: (u,v) ∈ E}, call the list of all adjacency vertices of u. In general element in Adj[u] is unordered In an undirected graph Sum(Adj[u], for all u ∈ V) = 2 |E| But in a directed graph Sum(Adj[u], for all u ∈ V) = 1 |E| 清华大学 宋斌恒 8 Data structure of Adjacency Data structure of Adjacency-list representation representation A set of vertex objects Vertex object contains one vertex u, and a set of vertices Adj[u], which contains all its adjacency vertices of u. ? Using what data structure to represent a set for the vertex objects ? Using what data structure to represent a set for Adj[u] 清华大学 宋斌恒 9 Weighted Graph Weighted Graph We can assign value to the edges of a graph, then we call such a graph is a weighted graph. Classically, a weighted graph has its edge value belong to R, but we can extend it to values from any particular spaces, say, spaces containing complex objects w: E ÆR is the weight function 清华大学 宋斌恒 10 Adjacency Adjacency-list representation for list representation for Weighted Graphics Weighted Graphics We reconstruct the set Adj[u] as Adj[u]={(v,r): v ∈ V, r ∈ R} where R is the space of real number or generally any object space 清华大学 宋斌恒 11 More general graphics More general graphics We can also assign values to the vertices of a graph, then it needs a more general representation to present such a graph !Give an Adjacency-list like data structure to represent such a graph. 清华大学 宋斌恒 12 Matrix representation Matrix representation A = (aij)n*n. aij = 1 if (i,j) ∈E, 0 else. It is called the adjacency matrix ?How to present it for the case of weighted graph? ?For more general case: there are information both on the vertices and edges?
BFS: Breadth first search 基本事实 1. BFS(G, s) -Given a graph represented by adjacency- For each vertex u E VIGHsI list, Compute the out-degree and in degree of every vertices 雾 Transpose of a graph 3.ds=0 where E2 is a set of (u, v) such that there exists at least one w in V such that both 4. s=null (u, w) and (w v) are in V. Give an algorithm to compute it 6. Q enqueue(s) BES while(Q=φ For each v∈Adul 日目日回 BFS续] BFS[续 日回 1(②② Q=r,wl Q=v,t,x ①(0② Q=w
3 清华大学 宋斌恒 13 基本事实 Given a graph represented by adjacencylist, Compute the out-degree and indegree of every vertices. Transpose of a graph Square of a directed graph: G2=(V,E2), where E2 is a set of (u,v) such that there exists at least one w in V such that both (u,w) and (w,v) are in V. Give an algorithm to compute it. 清华大学 宋斌恒 14 BFS: Breadth first search BFS: Breadth first search 1. BFS(G,s) 1. For each vertex u ∈ V[G]-{s} 1. Color[u]=white 2. d[u]=∞ 3. π [u]=null 2. color[s]=grey 3. d[s]=0 4. π [s]=null 5. Q=φ 6. Q.enqueue(s) 清华大学 宋斌恒 15 BFS 7. while(Q != φ) 1. u=Q.dequeue() 2. For each v ∈ Adj[u] 1. If (color[v] == white) 1. color[v]=gray 2. d[v]=d[u]+1 3. π [v]=u 4. Q.enqueue(v) 3. color[u]=black 清华大学 宋斌恒 16 BFS ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ v w r t u x y s ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ v w r t u x y s Q={} Q={s} 清华大学 宋斌恒 17 BFS[续] 1 0 ∞ ∞ ∞ 1 ∞ ∞ v w r t u x y s Q={r,w} 1 0 ∞ ∞ 2 1 ∞ ∞ v w r t u x y s Q={w,v} 清华大学 宋斌恒 18 BFS[续] 1 0 2 ∞ 2 1 2 ∞ v w r t u x y s Q={v,t,x} 1 0 2 ∞ 2 1 2 ∞ v w r t u x y s Q={t,x}
BFS[续] 2(1-(2 区 日日回 r st u y Analysis Shortest path -Using aggregate analysis, the complexity E什么是最短路径【 definition? of BFS iS O(E+V SBy a BFS, we got a shortest-path distance E: Can you? d(s, v) from s to v as the minimum numbe of edges in any path from vertex s to vertex v Erlf there is no path from s to v, then 6(s,V)=00 Lemma 22.1 Lemma 22.2 iLemma 22.1. if (u, VEEIGI, then o(s, v) -After the BFS run on the graph G from a ≤6(s,u)+1【三角不等式】 given source vertex s, then upon termination for each vertex v in V Y Case 1. u is reachable from s. then the ≥dv≥6(s,V) distance from v is less than the length of the shortest path to u+(u, v), hence aCase 2 u is not reachable from s, then
4 清华大学 宋斌恒 19 BFS[续] 1 0 2 3 2 1 2 ∞ v w r t u x y s Q={x,u} 1 0 2 3 2 1 2 3 v w r t u x y s Q={u,y} 清华大学 宋斌恒 20 BFS[续] 1 0 2 3 2 1 2 3 v w r t u x y s Q={y} 1 0 2 3 2 1 2 3 v w r t u x y s Q={} 清华大学 宋斌恒 21 Analysis Analysis Using aggregate analysis,the complexity of BFS is O(E+V). Can you? 清华大学 宋斌恒 22 Shortest path Shortest path 什么是最短路径【definition?】 By a BFS, we got a 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)=∞. 清华大学 宋斌恒 23 Lemma 22.1 Lemma 22.1 Lemma 22.1. if (u,v)∈E[G], then δ(s,v) ≤δ(s,u)+1【三角不等式】 Proof. Case 1. u is reachable from s, then the distance from v is less than the length of the shortest path to u + (u,v)，hence … Case 2. u is not reachable from s, then δ(s,u)=∞, hence … 清华大学 宋斌恒 24 Lemma 22.2 Lemma 22.2 After the BFS run on the graph G from a given source vertex s, then upon termination, for each vertex v in V, d[v]≥δ(s,v)
Proof 证明(续) By induction of the number of enqueue EiJust after the initializing, that is the time that s ed. We can verify that the FThe inductive hypothesis is that d[v]8(s, v) hypothesis is hold here for all v EV all the time while computin 【dv在下降】 2)dv=∞≥可s, 证明(续) 证明(续) FFor the inductive step, consider a white Efrom lemma 22.1. we obtain vertex v that is discovered during the search from a vertex u. The inductive Edv=du+1≥s,u]+1≥s hypothesis implies that edul≥als,u Z: Vertex v is enqueued, and d[] never changed during the following computing thus the hypothesis is maintained Lemma 22.3 EWhen v enqueues, the last dequeued element is u, now its head V, satisfies cLet G={v12……,},v1 is the head of the du]≤dl queue, and v, is the tail, then zdv+=dv=du+1≤dH+1 dvl≤dvl+ e-dv.[u+1(by induction) dvls dvi for all i= 1, 2,-,r-1 E:Implies d[v]sd[u+1 =d[v]= d[vr+1 &Hence the enqueue operation maintains the hypothesis 5
5 清华大学 宋斌恒 25 Proof By induction of the number of enqueue operations. The inductive hypothesis is that d[v]≥δ(s,v) for all v ∈V all the time while computing. 【d[v]在下降】 清华大学 宋斌恒 26 证明（续） Just after the initializing, that is the time that s enqueued. We can verify that the hypothesis is hold here: 1)d[s]= 0 = δ[s,s] 2)d[v]= ∞≥ δ[s,v] 清华大学 宋斌恒 27 证明（续） For the inductive step, consider a white vertex v that is discovered during the search from a vertex u. The inductive hypothesis implies that d[u] ≥ δ[s,u]. s v u 清华大学 宋斌恒 28 证明（续） from lemma 22.1, we obtain d[v]=d[u]+1≥ δ[s,u]+1 ≥ δ[s,v] Vertex v is enqueued, and d[v] never changed during the following computing, thus the hypothesis is maintained 清华大学 宋斌恒 29 Lemma 22.3 Lemma 22.3 Let Q={v1,v2,…,vr }, v1 is the head of the queue, and vr is the tail, then: d[vr ] ≤ d[v1]+1 d[vi ] ≤ d[vi+1] for all i = 1,2,…,r-1. 清华大学 宋斌恒 30 When v enqueues, the last dequeued element is u, now its head v1 satisfies d[u]≤d[v1]. d[vr+1]=d[v]=d[u]+1 ≤d[v1]+1 d[vr ]≤d[u]+1 (by induction) Implies d[vr ] ≤d[u]+1 =d[v]= d[vr+1] Hence the enqueue operation maintains the hypothesis. s v u Q={v1 ,…, vr, v} Q={u, v1 ,…, vr}
Corollary 22.4 Theorem 22.5 cdu][] if u enqueued before v F(Correctness of the BFS): Let G be a -Proof. Immediate from the above lemma directed or undirected graph, and suppose that BFS is run on G from a given s in V. During the searching, it discovers all the s reachable from s, and upon Proof of theorem 22.4 证明(续) 反证法:设顶点v是 的顶点之一,则d≠svl,很显然 Edy>s,=10.【利用 V≠s,由于d≥8s,得到:dv>8[s LV是从s可到达的,否则矛盾,故有最短路径 下边说明在u出队列之时,不论v是白、 到达v,且其前一个顶点为u【一定有】,进 黑,都矛盾 而得到:8s,V=8s,u]+1 d=du+1,【白即缺省色:蓝 灰:dv≤du+1 黑:dN≤du Breadth first tree Diameter of a tree s-The procedure BFS builds a breadth-first . The diameter of a tree T=(V, E)is given tree. s is the root EMax(6(u),foru,v∈V Give an efficient solution 2①2
6 清华大学 宋斌恒 31 Corollary 22.4 Corollary 22.4 d[u]≤d[v] if u enqueued before v. Proof. Immediate from the above lemma. 清华大学 宋斌恒 32 Theorem 22.5 Theorem 22.5 (Correctness of the BFS): Let G be a directed or undirected graph, and suppose that BFS is run on G from a given s in V. Then, During the searching, it discovers all the vertices is reachable from s, and upon termination, d[v] = δ(s,v) One of the shortest path from s to v contains (π[v],v) if v is reachable from s. 清华大学 宋斌恒 33 Proof of Theorem 22.4 Proof of Theorem 22.4 反证法：设顶点v是不满足以上定理的距离最 短的顶点之一，则d[v] ≠ δ[s,v], 很显然， v≠s, 由于d[v] ≥δ[s,v]得到： d[v] >δ[s,v]. v 是从s可到达的，否则矛盾，故有最短路径 到达v，且其前一个顶点为u【一定有】，进 而得到： δ[s,v] ＝δ[s,u]＋1Î s v u 清华大学 宋斌恒 34 证明（续） d[v]> δ[s,v] = δ[s,u]＋1=d[u]+1.【利用假 设】 下边说明在u出队列之时，不论v是白、 灰、黑，都矛盾： 白： d[v] = d[u]+1，【白即缺省色：蓝】 灰： d[v] ≤ d[u]+1, 黑： d[v] ≤ d[u]。 而不是 d[v]> d[u]+1 ！！ 清华大学 宋斌恒 35 Breadth first tree Breadth first tree The procedure BFS builds a breadth-first tree. s is the root. 1 0 2 3 2 1 2 3 v w r t u x y s 清华大学 宋斌恒 36 Diameter of a tree Diameter of a tree The diameter of a tree T = (V, E) is given by Max(δ(u,v), for u,v ∈V) Give an efficient solution
DFS: Depth-first search 1. DFS(G) For each vertex u∈vl S-visit(u white then
7 清华大学 宋斌恒 37 DFS: Depth DFS: Depth-first search first search 1/12 2/11 4/5 3/10 15/16 13/14 6/7 8/9 清华大学 宋斌恒 38 1. DFS(G) 1. For each vertex u ∈ V[G] 1. color[u]Åwhite 2. π[u]Ånull 2. timeÅ0 3. For each vertex u ∈ V[G] 1. If color[u] == white then DFS-Visit(u) 2. DFS-Visit(u) 1. color[u]Ågrey 2. time++ 3. d[u]Åtime 4. For each v ∈ Adj[u] 1. If color[v] == white then 1. π[v]Åu 2. DFS-Visit(v) 5. color[u]Åblack 6. time++ 7. f(u)Åtime 清华大学 宋斌恒 39 1/ 1/ 2/ 1/ 2/ 3/ 1/ 2/ 4/ 3/ 清华大学 宋斌恒 40 1/ 2/ 4/ 3/ 1/ 2/ 4/5 1/ 2/ 4/5 3/6 1/ 2/7 3/ 4/5 3/6 清华大学 宋斌恒 41 1/ 2/7 4/5 3/6 1/8 2/7 4/5 3/6 1/8 2/7 9/ 4/5 3/6 1/8 2/7 9/ 4/5 3/6 清华大学 宋斌恒 42 1/8 2/7 9/ 4/5 3/6 10/ 1/8 2/7 9/ 4/5 3/6 10/ 1/8 2/7 9/ 4/5 3/6 10/11 1/8 2/7 9/12 4/5 3/6 10/11
DFS: Depth-first search Properties of depth-first search F-To search as" deeper as possible Ea Theorem 22.7(Parenthesis theorem) for If there is more edges can explore during the any different vertices u and v in a graph, search, explore it. 2-DFS result The(d[u, fu) and (d(vl, fvI are disjoint or aIt compo DFS forest by a predecessor one contains another entirely 1. If(dqu, fu) contains(d[v fvn entirely, then v is (rvv)v∈ V and=nu the descendent of u in a depth- first tree,反之亦 the depth-first forest I the tree edges f(du fu) and (dv. fiv) are disjoint, then u and Theorem 22.9(White path theorem) Classification of edges S-Vertex v is a descendent of u. if at the ≥: Tree edges discovery time d[u of u, vertex v can be - Back edges reached from u along a path consisting entirely of white vertices Forward edges Cross edges Concepts on topological sort Topological sort ErOn a DAG-directed acyclic graph, it can Topological-sort(G) sort the vertices in an ordered sequence such that all of the edges is a subset of 1. Call DFS(G) l(u,v): u appears earlier than v At each vertex is finished, insert it onto the front of a linked list 3 Return the linked list
8 清华大学 宋斌恒 43 DFS: Depth DFS: Depth-first search first search To search as “deeper” as possible: If there is more edges can explore during the search, explore it. DFS result: It composes a DFS forest by a predecessor π. Gπ=(V,Eπ), where Eπ={(π[v],v): v ∈ V and π[v] != null} Gπ call the depth-first forest Eπ call the tree edges 清华大学 宋斌恒 44 Properties of depth Properties of depth-first search first search Theorem 22.7 (Parenthesis theorem) for any different vertices u and v in a graph, after a DFS, it satisfies: 1. The (d[u],f[u]) and (d[v],f[v]) are disjoint or one contains another entirely. 1. If (d[u],f[u]) contains (d[v],f[v]) entirely, then v is the descendent of u in a depth-first tree，反之亦 然 2. If (d[u],f[u]) and (d[v],f[v]) are disjoint, then u and v are not descendent each other. 清华大学 宋斌恒 45 Theorem 22.9 (White path Theorem 22.9 (White path theorem) theorem) Vertex v is a descendent of u, if at the discovery time d[u] of u, vertex v can be reached from u along a path consisting entirely of white vertices. 清华大学 宋斌恒 46 Classification of edges Classification of edges Tree edges Back edges Forward edges Cross edges 1/8 2/7 9/12 4/5 3/6 10/11 清华大学 宋斌恒 47 Concepts on topological sort Concepts on topological sort On a DAG – directed acyclic graph, it can sort the vertices in an ordered sequence such that all of the edges is a subset of {(u,v): u appears earlier than v} 1/8 2/7 9/12 4/5 3/6 10/11 1/8 2/7 9/12 4/5 3/6 10/11 清华大学 宋斌恒 48 Topological sort Topological sort Topological-sort(G) 1. Call DFS(G) 2. At each vertex is finished, insert it onto the front of a linked list 3. Return the linked list
ma22.11 Theorem 22.12 A directed graph G is acyclic if and only if 2 Topological-Sort(G) produces a a depth-first search of G yields no back al sort of a directed acyclic graph G C Proof. It makes a cycle in the graph if there exists a back edges 证明 穿衣实例 设DFS在图G=(E运行完毕并得到所有顶点的 我们只需要证明对任意的边(uv)都有 这能实 面(uv)成为回退边矛盾,故v只 是白的,它将成为u的孩子【后代】,故有 色,则它已经被搜索完毕,而u还未结束,故 逆挂列后所有的边将有序 Strongly connected components a Strongly-Connected-Components(G 1. Call DFS(G) to compute finishing time f[u 强连通分支 2. Compute G Definition: in a directed graph, a strongly 3. Call DFS(G), but in the main loop of DFS connected component contains maximal the vertices is selected in the order of set of vertices C subset of V such that fo decreasing f[u every pair of vertices u and v in C, we 4. Output the vertices of each tree in the second DFS(G), we got the separate have both u -->v and v->u trongly connected components
9 清华大学 宋斌恒 49 Lemma22.11 Lemma22.11 A directed graph G is acyclic if and only if a depth-first search of G yields no back edges Proof. It makes a cycle in the graph if there exists a back edges. 清华大学 宋斌恒 50 Theorem 22.12 Theorem 22.12 Topological-Sort(G) produces a topological sort of a directed acyclic graph G. 清华大学 宋斌恒 51 证明 设 DFS 在图G=(V,E)运行完毕并得到所有顶点的 完成时间。我们只需要证明对任意的边(u,v)都有 f[v]v and v -->u. 清华大学 宋斌恒 54 Strongly-Connected-Components(G) 1. Call DFS(G) to compute finishing time f[u] 2. Compute GT 3. Call DFS(GT), but in the main loop of DFS, the vertices is selected in the order of decreasing f[u] 4. Output the vertices of each tree in the second DFS(GT), we got the separate strongly connected components
强连通分支的性质 Lemma 22.13 Component Graph: GSCC=(VSCC,EScC) ≥如果C和C是图G的两个不同的强连通分 where Vscc is the representation of the 支,设u,V属于C:u,V属于C,若有u到 strongly connected component, ESCc is the u的通路,则必没有v到v的通路 representation of the edges between the z证明:平凡 components Is a dag eTwo way connection 引理22.14 推论22.15 设C和C是图G的两个强连通分支,设(uV) E对于G则上述引理的不等式正好相反 是一条连接C和C的边,其中u属于C,V属 证明:平凡 于C,则当DFS完成后有:f(C)>f(C) 情况1:C中元素首先发现:白色路径定理 情况2:C中元素首先发现:C完成后才能进入 定理2216 证明(续 家上述算法可以得到一个图的强连通分支 此时,C中其它顶点必为白色,由白色路径 E证明:提示:对GT上进行DFS过程中生产 定理得知,C中的其它顶点一定是此次DFS 的每一棵树是强连通分支进行归纳法 搜索中u的后代 k=0即开始时是正确的【平凡】 另外,所有GT其它从C引出的边都在已经发 设前k棵树是强连通分支,我们来分析第k+ 现的强连通分支内,故不会有其它非C的未 棵树:设此树之根为u,而u在图的强连通分支 访问的点在完成u的搜索中被访问到。 即u为根的树是G的一个强连通分支 u=C)>1(C),其中C是任何没有被发现的连通 10
10 清华大学 宋斌恒 55 强连通分支的性质 Component Graph: GSCC=(VSCC,ESCC), where VSCC is the representation of the strongly connected component, ESCC is the representation of the edges between the components. GSCC is a dag. Two way connection 清华大学 宋斌恒 56 Lemma 22.13 Lemma 22.13 如果C和C’是图G的两个不同的强连通分 支，设u， v属于C；u’, v’属于C’，若有u到 u’的通路，则必没有v’到v的通路。 证明：平凡 清华大学 宋斌恒 57 引理22.14 设C和C’是图G的两个强连通分支，设(u,v) 是一条连接C和C’的边，其中u属于C，v属 于C’，则当DFS完成后有：f(C)>f(C’). 证明： 情况1：C中元素首先发现：白色路径定理 情况2：C’中元素首先发现：C’完成后才能进入 C 清华大学 宋斌恒 58 推论22.15 对于GT则上述引理的不等式正好相反。 证明：平凡 清华大学 宋斌恒 59 定理22.16 上述算法可以得到一个图的强连通分支。 证明：提示：对GT上进行DFS过程中生产 的每一棵树是强连通分支进行归纳法。 k＝0即开始时是正确的【平凡】 设前k棵树是强连通分支，我们来分析第k＋1 棵树：设此树之根为u，而u在图的强连通分支 C内，故有 f[u]=f(C)>f(C’),其中C’是任何没有被发现的连通 分支 清华大学 宋斌恒 60 证明（续） 此时，C中其它顶点必为白色，由白色路径 定理得知，C中的其它顶点一定是此次DFS 搜索中u的后代， 另外，所有GT其它从C引出的边都在已经发 现的强连通分支内，故不会有其它非C的未 访问的点在完成u的搜索中被访问到。 即u为根的树是G的一个强连通分支