数据结构（双语）48课时版15-16-Graph Algorithms.ppt

Data Structure数据结构,计算机与信息技术系 袁莹 Email: 2021年6月8日,9 Graph Algorithms,9.1 Definitions 9.2 Topological Sort 9.3 Shorted-Path Algorithms 9.5 Minimum Spanning Tree 参考中文书第6章：6.1/6.2.1/6.2.2/6.4/6.5.1/6.6,CHAPTER 9 GRAPH ALGORITHMS,terminology： graph 图 vertex 顶点 edge 边 directed 有向的 adjacent 邻接 weight/cost 权值 path 路径 length 长度,loop 环 cycle 圈 acyclic 无圈的 connected 连通的 strongly connected 强连通的 weakly connected 弱连通的 complete graph 完全图,CHAPTER 9 GRAPH ALGORITHMS,1 Definitions, G( V, E ) where G := graph, V = V( G ) := finite nonempty set of vertices, and E = E( G ) := finite set of edges., Undirected graph: ( vi , vj ) = ( vj , vi ) := the same edge., Restrictions : (1) Self loop is illegal. (2) Multigraph is not considered, Complete graph: a graph that has the maximum number of edges, Subgraph G G := V( G ) V( G ) out-degree(v) = 1; degree(v) = 4, Given G with n vertices and e edges, then, A DAG := a directed acyclic graph,1 Definitions, Representation of Graphs,Adjacency Matrix,adj_mat n n is defined for G(V, E) with n vertices, n 1 :,Note: If G is undirected, then adj_mat is symmetric. Thus we can save space by storing only half of the matrix.,I know what youre about to say: this representation wastes space if the graph has a lot of vertices but very few edges, right?,Hey you begin to know me! Right. And it wastes time as well. If we are to find out whether or not G is connected, well have to examine all edges. In this case T and S are both O( n2 ),The trick is to store the matrix as a 1-D array: adj_mat n(n+1)/2 = a11, a21, a22, ., an1, ., ann The index for aij is ( i ( i 1 ) / 2 + j ).,1 Definitions,Adjacency Lists,Replace each row by a linked list,Example,Note: The order of nodes in each list does not matter.,For undirected G: S = V+2E For directed G: S = V+E,Exercise,Adjacency Matrix,Adjacency Lists,Space,2 Topological Sort,Example Courses needed for a computer science degree at a hypothetical university,How shall we convert this list into a graph?,2 Topological Sort, i is a predecessor of j := there is a path from i to j i is an immediate predecessor of j := E( G ) Then j is called a successor ( immediate successor ) of i,Feasible AOV network must be a DAG (directed acyclic graph).,（AOV: Activity On Vertex network）,2 Topological Sort,【Definition】A topological order is a linear ordering of the vertices of a graph such that, for any two vertices, i, j, if i is a predecessor of j in the network then i precedes j in the linear ordering.,Example One possible suggestion on course schedule for a computer science degree could be:,2 Topological Sort,Note: The topological orders may not be unique for a network. For example, there are several ways (topological orders) to meet the degree requirements in computer science.,Goal,Test an AOV for feasibility, and generate a topological order if possible.,void Topsort( Graph G ) int Counter; Vertex V, W; for ( Counter = 0; Counter NumVertex; Counter + ) V = FindNewVertexOfInDegreeZero( ); if ( V = NotAVertex ) Error ( “Graph has a cycle” ); break; TopNum V = Counter; /* or output V */ for ( each W adjacent to V ) Indegree W ; ,/* O( |V| ) */, T = O( |V|2 ),AOV Network,topological order,V6 V1 V4 V3 V2 V5,不唯一！, Exercise：AOV Network - topological order,2 Topological Sort, Improvement: Keep all the unassigned vertices of degree 0 in a special box (queue or stack).,void Topsort( Graph G ) Queue Q; int Counter = 0; Vertex V, W; Q = CreateQueue( NumVertex ); MakeEmpty( Q ); for ( each vertex V ) if ( Indegree V = 0 ) Enqueue( V, Q ); while ( !IsEmpty( Q ) ) V = Dequeue( Q ); TopNum V = + Counter; /* assign next */ for ( each W adjacent to V ) if ( Indegree W = 0 ) Enqueue( W, Q ); /* end-while */ if ( Counter != NumVertex ) Error( “Graph has a cycle” ); DisposeQueue( Q ); /* free memory */,v1,0,v2,1,2,1,0,v5,0,v4,1,v6,0,v3,2,0,v7,1,0,T = O( |V| + |E| ),Mistakes in Fig 9.4 on p.287,3 Shortest Path Algorithms,Given a digraph G = ( V, E ), and a cost function c( e ) for e E( G ). The length of a path P from source to destination is (also called weighted path length).,1. Single-Source Shortest-Path Problem,Given as input a weighted graph, G = ( V, E ), and a distinguished vertex, s, find the shortest weighted path from s to every other vertex in G.,Negative-cost cycle,Note: If there is no negative-cost cycle, the shortest path from s to s is defined to be zero.,3 Shortest Path Algorithms, Unweighted Shortest Paths,0,0: v3,1: ,v1 and v6,1,1,2: ,v2 and v4,2,2,3: ,v5,and v7,3,3, Sketch of the idea,Breadth-first search, Implementation,Table i .Dist := distance from s to vi /* initialized to be except for s */,Table i .Known := 1 if vi is checked; or 0 if not,Table i .Path := for tracking the path /* initialized to be 0 */,3 Shortest Path Algorithms,void Unweighted( Table T ) int CurrDist; Vertex V, W; for ( CurrDist = 0; CurrDist NumVertex; CurrDist + ) for ( each vertex V ) if ( !T V .Known /* end-if Dist = Infinity */ /* end-if !Known Vertex V, W; Q = CreateQueue (NumVertex ); MakeEmpty( Q );。