内容提要 第七讲图的基本算法 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}