《计算机组成与结构：DS and AL_Lecture7_Graph》由会员分享，可在线阅读，更多相关《计算机组成与结构：DS and AL_Lecture7_Graph（109页珍藏版）》请在金锄头文库上搜索。
1、DATA STRUCTURES ANDALGORITHMSLecture Notes 7buptsse2ROAD MAPGRAPH ALGORITHMSBasic TerminologyGraph Implementation Traversing GraphConnectivityApplication of Graph3Graph Terminology1) DefinitionA graph G consists of two setsa finite, nonempty set of vertices V(G)a finite, possible empty set of edges
2、E(G)G(V,E) represents a graphThe number of vertices is written |V|, and the number edges is written |E|.General graphs differ from trees need not have a root nodeno implicit parent-child relationshipmay be several (or no) paths from one vertex to another. w1w4w5w2w34Graph Terminology1) DefinitionFor
3、 A directed graphIf u,v are two vertices then is a arc (edge), u is called as tail, v is called as head.V1V4V5V2V3uv5An undirected graph is one in which the pair of vertices in a edge is unordered, (v0, v1) = (v1,v0) A directed graph is one in which each edge is a directed pair of vertices, != A com
4、plete graph is a graph that has the maximum number of edgesfor undirected graph with n vertices, the maximum number of edges is n(n-1)/2for directed graph with n vertices, the maximum number of edges is n(n-1)If the edges of a graph is enlog(n), the graph is called Sparse graph ,otherwise, it is cal
5、led as Dense Graph Graph Terminology6Examples for GraphV(G1)=0,1,2,3 E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)V(G2)=0,1,2,3,4,5,6 E(G2)=(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)V(G3)=0,1,2 E(G3)=,V(G4)=0,1,2,3 E(G4)=, , ,7Adjacent(相邻） and Incident（关联）If (v0,v1) is an edge in an undirected graph, v0 and v1
6、 are adjacent(相邻点）The edge (v0, v1) is incident（相关联） on vertices v0 and v1If is an edge in a directed graphv0 is adjacent to v1, and v1 is adjacent from v0The edge is incident on v0 and v1Weighted digraph:there is some “cost” or “weight” associated with each edge.A subgraph of G is a graph G such th
7、at V(G) is a subset of V(G) and E(G) is a subset of E(G)Graph Terminology8The degree of a vertex is the number of edges incident to that vertexFor directed graph, the in-degree of a vertex v is the number of edges that have v as the headthe out-degree of a vertex v is the number of edges that have v
8、 as the tailif di is the degree of a vertex i in a graph G with n vertices and e edges, the number of edges isGraph Terminology9undirected graphdegree012345632331111directed graphin-degreeout-degree012in:1, out: 1in: 1, out: 2in: 1, out: 0012333310A path from vertex vp to vq in a graph G is a sequen
9、ce of vertices, vp, vi1, vi2, ., vin, vq, such that (vp, vi1), (vi1, vi2), ., (vin, vq) are edges in an graph.The length of a path is the number of edges on itA simple path/ cycle is a path in which all vertices, except possibly the first and the last, are distinctA cycle is a simple path in which t
10、he first and the last vertices are the sameGraph Terminology11An undirected graph is connected if there is a path from every vertex to every other vertex.（联通图）A directed graph with this property is called strongly connected.（强联通图）If a directed graph is not strongly connected, but the underlying grap
11、h (without direction to the arcs) is connected, then the graph is said to be weakly connected.A complete graph is a graph in which there is an edge between every pair of vertices.Graph Terminology12connected245136strongly connected.356UnconnectedTwo connected partsExamples24513613GRAPH ExamplesTraff
12、ic flow can be modeled by a graphEach street intersection represents a vertex, each street is an edge.Edge costs could represent, among other things, a speed limit or capacityWe could ask for the shortest route or use this information to find the most likely location for bottleneck142 2）ADT of ADT o
13、f GraphGraph ADT Graph ADT Graph Objects:Objects: a a nonempty nonempty set set of of vertices vertices and and a a set set of of edges, edges, where where each each edge is a pair of verticesedge is a pair of vertices Functions: for all Functions: for all graphgraph Graph, v, v1 and v2Graph, v, v1
14、and v2 VerticesVertices Graph Create():Graph Create(): return an empty graphreturn an empty graph Graph DeleteEdge(graph, v1, v2): Graph DeleteEdge(graph, v1, v2): return a graph in which return a graph in which the edge (v1, v2) is removed the edge (v1, v2) is removed Boolean IsEmpty(graph): Boolea
15、n IsEmpty(graph): if (graph=empty graph) return if (graph=empty graph) return TRUE; else return FALSE TRUE; else return FALSE ADT Graph ADT GraphADT of Graph15ROAD MAPGRAPH ALGORITHMSBasic TerminologyGraph Implementation Traversing GraphConnectivityApplication of Graph16Graph Implementation1) Defini
16、tion: Let G=(V,E) be a graph with n vertices.The adjacency matrix of G is a two-dimensional n by n array, say AAn n n n AdjacencyMatrix（Array）Foraweighteddigraph17Examples for Adjacency MatrixTheadjacencymatrixforanundirectedgraphissymmetric;theadjacencymatrixforadigraphneednotbesymmetric18For a wei
17、ghted digraph theweightoftheedgefromvertexitovertexjisusedinsteadof1intheadjacencymatrix.192) Merits of Adjacency MatrixFrom the adjacency matrix, to determine the connection of vertices is easyThe degree of a vertex is For a directed digraph, the sum of 1 (or true) in row i of the adjacency matrix
18、is yields the out-degree of the ith vertex.The sum of the entries in the ith column is its in-degree.AdjacencyMatrix203) Declaration#define MaxVNum 100 #define MaxVNum 100 /*/*最大顶点数设为最大顶点数设为最大顶点数设为最大顶点数设为100*/100*/typedef XXX VertexType; typedef XXX VertexType; /*/*顶点类型顶点类型顶点类型顶点类型* */ /typedef int
19、EdgeType; typedef int EdgeType; /*/*边的权值设为整型边的权值设为整型边的权值设为整型边的权值设为整型* */ /邻接矩阵类型：邻接矩阵类型：邻接矩阵类型：邻接矩阵类型： typedef struct ArcCell typedef struct ArcCell VertexType VertexType adj;adj; /* 顶点关系类型。对无权图，用(是)或(否)表示相邻否；对带权图，则为权值*/ InfoType *Info; InfoType *Info; / / 存弧相关信息存弧相关信息存弧相关信息存弧相关信息, , 该弧相关信息的指针(可无) /
20、 ArcCell, AdjMatrixMaxVNumMaxVNum ArcCell, AdjMatrixMaxVNumMaxVNum 图类型：图类型：图类型：图类型： typedef structtypedef struct VertexType vexsMaxVNum; VertexType vexsMaxVNum; /*/*顶点表顶点表顶点表顶点表* */ / AdjMatrix arcs; AdjMatrix arcs; /*/*邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表* */ / int vexnum, arcnum; int vexnum, arcnum; /
21、*/*图的顶点数和边数图的顶点数和边数图的顶点数和边数图的顶点数和边数* */ / Mgragh; Mgragh; /*Maragh/*Maragh是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图* */ /AdjacencyMatrix214) Create a GraphAdjacencyMatrix22CreateGraph (Maragh &ga) int i, j, k; float w; scanf ( &ga.vexnum, &ga.arcnum); for ( i=0; i vexsigetchar(); /*读入顶点信息，建立顶点表读入顶点信息
22、，建立顶点表*/ for ( i=0; i ga.vexnum ; i+) for (j=0; j arcsij0; /*邻接矩阵初始化邻接矩阵初始化*/ for ( k=0; k ga.arcnum; k+) scanf (&v1, &v2, &w); /*读入一条边的顶点和权值读入一条边的顶点和权值*/ i=LocateVex(ga,v1); j=LocateVex(ga,v2); ga.arcsij.adj w; ga. arcsji.adjw; AdjacencyMatrix23Adjacency ListIfagraphdoesnothavemanyedges,theadjacenc
23、ymatrixwillbesparsesuchrepresentationisawasteofspaceuseanarrayofpointerstolinkedrow-listsadjacency-listrepresentationfordigraphs.24Each row in adjacency matrix is represented as an adjacency list.The graph is represented by an array or vector v1, v2,.,vn, one element for each vertex in the digraph.
24、Each vi stores the data stored in vertex i together with a linked list of the numbers of all vertices adjacent to vertex i. 1) Description of Adjacency ListAdjacency List25Example262) Merits of Adjacency Matrixdegree of a vertex in an undirected graph# of nodes in adjacency listout-degree of a verte
25、x in a directed graph# of nodes in its adjacency listin-degree of a vertex in a directed graphtraverse the whole data structure27Inverse adjacency listG1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next283) Declarationdefine MaxVerNum 100 /*define MaxVerNum 100 /*最大顶点数为最大顶点数为最大顶点数为最大顶点数为100*/100*/邻接表类
26、型邻接表类型邻接表类型邻接表类型 ： typedef struct ArcNodetypedef struct ArcNode int adjvex; /* int adjvex; /*邻接点域邻接点域邻接点域邻接点域* */ / InfoType *Info; /* InfoType *Info; /*表示边上信息的域表示边上信息的域表示边上信息的域表示边上信息的域info*/info*/ struct ArcNode * next; /* struct ArcNode * next; /*指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域* *
27、/ / ArcNode ; ArcNode ; 表头结点类型表头结点类型表头结点类型表头结点类型 ： typedef struct Vnodetypedef struct Vnode VertexType vertex; /* VertexType vertex; /*顶点域顶点域顶点域顶点域* */ / ArcNode * firstedge; /* ArcNode * firstedge; /*边表头指针边表头指针边表头指针边表头指针* */ / Vnode, AdjList MaxVertexNum; Vnode, AdjList MaxVertexNum; 图的类型图的类型图的类型图的
28、类型 ： typedef structtypedef struct AdjList vertices; /* AdjList vertices; /*邻接表邻接表邻接表邻接表* */ / int vexnum, arcnum; /* int vexnum, arcnum; /*顶点数和边数顶点数和边数顶点数和边数顶点数和边数* */ / ALGraph; /*ALGraph ALGraph; /*ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型* */ /29ROAD MAPGRAPH ALGORITHMSBasic Ter
29、minologyGraph Implementation Traversing GraphConnectivityApplication of Graph30 Graph TraversalsSome applications require visiting every vertex in the graph exactly once.The application may require that vertices be visited in some special order based on graph topology.depth-first search breadth-firs
30、t search31Depth-First Search1) Basic Idea：Start from a given vertex v and visit it. Start from a given vertex v and visit it. Visit the first neighbor, w, of v. Then visit the first Visit the first neighbor, w, of v. Then visit the first neighbor of w that has not already been visited, etc. neighbor
31、 of w that has not already been visited, etc. If a node with no unexamined neighbors, then backup If a node with no unexamined neighbors, then backup to the last visited node and examine its remaining to the last visited node and examine its remaining neighbors.neighbors.The search continues until a
32、ll nodes of the graph have The search continues until all nodes of the graph have been examined.been examined.32Example:V1V2V4V5V3V7V6V8V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8V1 V2 V4 V8 V3 V6 V7 V5Depth-First Search33A A、B B、D D、C CExample:Depth-First Search342) AlgorithmDifficultiesDifficulties：Ho
33、w to determine whether How to determine whether v v has been visited?has been visited? How to search the How to search the neighbor neighbor of vof v？SolutionsSolutions：Using an array Using an array visitednvisitedn. When . When i-thi-th vertex has been vertex has been visited, visited, visitedi=1.v
34、isitedi=1.Varying by different data structureVarying by different data structure： Adjacency MatrixAdjacency Matrix： Adjacency ListAdjacency List：Depth-First Search35DFS uses backtracking. Recursion is a natural DFS uses backtracking. Recursion is a natural technique for such problems.technique for s
35、uch problems.a stack is automatically maintained to make backtracking a stack is automatically maintained to make backtracking possible.possible.DFSDFSVisit the start vertex v.Visit the start vertex v.For each vertex w adjacent to v do:For each vertex w adjacent to v do: If w has not been visited, I
36、f w has not been visited, apply the depth-first search algorithmapply the depth-first search algorithm with w as the start vertex. with w as the start vertex. Depth-First Search36开始开始访问访问Vi,置置标志标志求求Vi邻接点邻接点有邻接点有邻接点W求下一邻接点求下一邻接点W ViW访问过访问过结束结束NYNYDFS开始开始标志数组初始化标志数组初始化Vi=0Vi访问过访问过DFSVi=Vi+1Vi=Vexnums结
37、束结束NNYYFlow RepresentationDFSTraverseVariables：Boolean visitedMAX ; /用于标识结点是否已被访问过用于标识结点是否已被访问过 voidDFSTraverse(GraphG)for(k=1;k=G.vexnum;+k)visitedk=FALSE;for(k=1;k0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);37Implementation of Depth-First Search38intFirstAdjVex(ALGraphG,intv)/返回返回G中第中第v个顶点的第个顶点的第1个
38、邻接点的序号。如果个邻接点的序号。如果v无邻接点，返回无邻接点，返回0。if(!G.verticesv.firstarc)return(0);elsereturn(G.verticesv.firstarc-adjvex);intNextAdjVex(ALGraphG,intv,intw)/返回返回G中第中第v个顶点的相对于顶点个顶点的相对于顶点w的下一个邻接点的序号。的下一个邻接点的序号。/如果如果v无相对于顶点无相对于顶点w的下一个邻接点，返回的下一个邻接点，返回0。ArcNode*p;p=G.vetricesv.firstarc;while(p&p-adjvex!=w)p=p-nextar
39、c;if(p-adjvex=w&p-nextarc)return(p-nextarc-adjvex);elsereturn(0);38Implementation of Depth-First Search393)Algorithm Analysis Let G=(V,E) be a graph with n vertices and e edges.Adjacency list: O(O(n n+ +e e) )。Adjacency matrix:O(O(n n2 2) )。Depth-First Search40Breadth-First Search1) Basic Idea：Start
40、 from a given vertex Start from a given vertex v v and visit it. and visit it. Visit all neighbors of Visit all neighbors of v v. .Then visit all neighbors of first neighbor Then visit all neighbors of first neighbor ww of of v v. .Then visit all neighbors of second neighbor Then visit all neighbors
41、 of second neighbor x x of of v v, etc. , etc. 41Example:V1V2V4V5V3V7V6V8BFS：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8BFS：V1 V2 V3 V4 V6 V7 V8 V5Breadth-First Search42Example:BFSBFS：A A、B B、C C、D DBreadth-First Search43BFS visits nodes level by level.BFS visits nodes level by level.While visiting each
42、 node on a given levelWhile visiting each node on a given level, store it store it so that, we can return to it after completing this levelso that, we can return to it after completing this levelso that nodes adjacent to it can be visited.so that nodes adjacent to it can be visited. Because the firs
43、t node visited on a given level Because the first node visited on a given level should be the first one to which we return, a should be the first one to which we return, a queuequeue is an appropriate data structure for storing the is an appropriate data structure for storing the nodes.nodes. 2) Alg
44、orithmBreadth-First Search44BFSVisit the start vertex Visit the start vertex v v. . Initialize a queue to contain only the start Initialize a queue to contain only the start vertex.vertex.While the queue is not empty do:While the queue is not empty do: Remove a vertex Remove a vertex v v from the qu
45、eue. from the queue. For all vertices For all vertices ww adjacent to adjacent to v v do: do: If w has not been visited thenIf w has not been visited theni. i. Visit Visit ww. .ii. Add ii. Add ww to the queue. to the queue.Breadth-First SearchvoidBFSTraverse(GraphG)for(v=1;v=G.vexnum;+v)visitedv=FAL
46、SE;InitQueue(Q);for(v=1;v0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;VISIT(w);EnQueue(Q,w);/endwhile/endifVariables：Boolean visitedMAX ; /用于标识结点是否已被访问过用于标识结点是否已被访问过 45Implementation of Breadth-First Search46开始开始标志数组初始化标志数组初始化Vi=0Vi访问过访问过BFSVi=Vi+1Vi=Vexnums结束结束NNYYGraph TraversalGraph TraversalI
47、nitialize an array or vector Initialize an array or vector unvisited: visitedi false for each unvisited: visitedi false for each vertex i.vertex i.While some element of unvisited While some element of unvisited is false, do:is false, do: Select an unvisited vertex v.Select an unvisited vertex v. Use
48、 BFS (or DFS) to visit all Use BFS (or DFS) to visit all vertices reachable from v. vertices reachable from v. Breadth-First Search47 BFS AlgorithmBFS Algorithm开始开始访问访问Vi,置置标志标志求求V邻接点邻接点WW存在吗存在吗V下一邻接点下一邻接点WW访问过访问过结束结束NYNY初始化队列初始化队列Vi入队入队队列空吗队列空吗队头队头V出队出队访问访问W,置置标志标志W入队入队NaaY48ROAD MAPGRAPH ALGORITHM
49、SBasic TerminologyGraph Implementation Traversing GraphConnectivityApplication of Graph49ConnectivityConnected division of undirected graph and spanning tree V1V2V4V5V8V3V6V7Depth-First spanning treeV1V2V4V5V8V3V6V7Breadth-First spanning treeV1V2V4V5V8V3V6V750 Connectivity Connected ComponentsIn an
50、undirected graph G, two vertices, v0 and v1, are connected if there is a path in G from v0 to v1. An undirected graph is connected if, for every pair of distinct vertices vi, vj, there is a path from vi to vj.A connected component of an undirected graph is a maximal connected subgraph.Any connected
51、graph with n vertices must have at least n-1 edges.51A directed graph is strongly connected if there is a directed path from vi to vj and also from vj to vi. A strongly connected component is a maximal subgraph that is strongly connected.When graph G is connected, a depth first or breadth first sear
52、ch starting at any vertex will visit all vertices in GConnectivity52连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分量连通分量例例245136Connectivity53Minimal Cost Spanning Trees(最小代价生成树）最小代价生成树）1) Spanning Trees(生成树）A spanning tree is any tree that consists solely of edges in G and that includes all the vertices.E(G
53、): T (tree edges) + N (nontree edges) where T: set of edges used during search N: set of remaining edgesA spanning tree is a minimal subgraph, G, of G such that V(G)=V(G) and G is connected.54Examples of Spanning Tree0123012301230123G1Possible spanning trees55Either DFS or BFS can be used to create
54、a spanning treeWhen DFS is used, the resulting spanning tree is known as a depth first spanning treeWhen BFS is used, the resulting spanning tree is known as a breadth first spanning treeWhile adding a nontree edge into any spanning tree, this will create a cycleSpanning Trees56V1V2V4V5V3V7V6V8Examp
55、leDFS：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8depthfirstspanningtreeV1V2V4V5V3V7V6V8breadthfirstspanningtreeV1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8BFS：V1 V2 V3 V4 V5 V6 V7 V857ExampleABLMCFDEGHKIJABLMCFJDEGHKIdepthfirstspanningforest582) Minimal Cost Spanning TreesThe cost of a spanning tree of a weighted u
56、ndirected graph is the sum of the costs of the edges in the spanning treeA minimal cost spanning tree is a spanning tree of least costTwo different algorithms can be usedPrimKruskalSelect n-1 edges from a weighted graphof n vertices with minimal cost.59Greedy StrategyAn optimal solution is construct
57、ed in stagesAt each stage, the best decision is made at this timeSince this decision cannot be changed later, we make sure that the decision will result in a feasible solutionTypically, the selection of an item at each stage is based on a least cost or a highest profit criterion60Prims IdeaLet Graph
58、 G = V,E, the minimum cost spanning tree be T=U,TE and U=V, TE E. Initially, U=u0, TE=;Adding edge and vertices to T one at a time.Select the least cost edge (u,v) that uU and v U. Adding v to U and (u,v) to TE;It continue, until n-1 edges have been selected and U=V61Examples for Prims Algorithm1654
59、32651356642513116314164314211643214251654321425362Prims AlgorithmThe minimum cost spanning tree T=U,TE ;U=u0; TE= ;while ( T contains fewer than n-1 edges) let (u,v) be a least cost edge such that uU and v U if (there is no such edge ) break; add v to U; add (u,v) to TE; if ( T contains fewer than n
60、-1 edges) printf(“No spanning treen”);63Kruskals IdeaBuild a minimum cost spanning tree T by adding edges to T one at a time.Select the edges for inclusion in T in non-decreasing order of the cost.An edge is added to T if it does not form a cycle.Since G is connected and has n 0 vertices, exactly n-
61、1 edges will be selected.64Examples for Kruskals Algorithm165432651356642516543212345应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程6566Kruskals AlgorithmT= ;while ( T contains less than n-1 edges & E is not empty) choose a least cost edge (v,w) from E; delete (v,w) from E; If (v,w) does not create a cycle i
62、n T) add (v,w) to T else discard (v,w); if (T contains fewer than n-1 edges) printf (“No spanning treen”);67ROAD MAPGRAPH ALGORITHMSBasic TerminologyGraph Implementation Traversing GraphConnectivityApplication of Graph68 Application of GraphApplication of directed acyclic graphTopological sortCritic
63、al path.Shortest-Path algorithms69Application of directed acyclic graph(有向无环图)How can we know whether there exist cycles or not?Directed treeDAG（DirectedAcycline Graph）A Directed Graph70Application of directed acyclic graph Topological SortAn ordering of vertices in a directed acyclic graph, such th
64、at if there is a path from vi to vj, then vj appears after vi in the ordering.C12C10C11C9C1C2C3C4C6C5C7C8C1,C9, # C2,C4,C10,C11, # C3,C12,C6, # C5, C7,C871Application of directed acyclic graph Topological SortAOV-Network (Activity on Vertex)Topological ordering is not possible if there is a cycle in
65、 the graph. 72 Application of directed acyclic graph Topological SortA simple algorithmCompute the indegree of all vertices from the adjacency information of the graph.Find any vertex with no incoming edges.Print this vertex, and remove it, and its edges.Apply this strategy to the rest of the graph.
66、Running time is (|V|2).73Application of directed acyclic graph Topological Sort/* Simple topological sort */Assuming that the Indegree array is initialized and the graph is read into an adjacency listvoid Topsort (Graph G) int Counter; Vertex V, W; for (Counter=0; CounterNumVertex; counter+) / V = F
67、indNewVertexOfInDegreeZero ();/scan the Indegree array looking for a vertex with indegree 0/ that has not been assigned a topological number.74Application of directed acyclic graph Topological Sort if (V = NotAVertex) Error (Graph has a cycle); break; TopNum V = Counter;/输出的顺序 for each W adjacent to
68、 V Indegree W -; O（n2)75 Application of directed acyclic graph Topological SortAn improved algorithmKeep all the unassigned vertices of indegree 0 in a queue.While queue not emptyRemove a vertex in the queue.Decrement the indegree of all adjacent vertices.If the indegree of an adjacent vertex become
69、s 0, enqueue the vertex.The topological ordering is the order in which the vertices dequeue,Running time is (|E|+|V|).76 Application of directed acyclic graph Topological Sort/* Figure 9.7 Pseudocode for Topological sort */void Topsort (Graph G) Queue Q; int Counter = 0; Vertex V, W; Q = CreateQueue
70、 (NumVertex); MakeEmpty (Q); for each vertex V if (Indegree V = 0)77 Enqueue (V, Q); while (!IsEmpty (Q) V = Dequeue (Q); TopNum V = +Counter; /* Next No. */ for each W adjacent to V if (-Indegree W = 0) Enqueue (W, Q); Application of directed acyclic graph Topological Sort78 if (Counter != NumVerte
71、x) Error (Graph has a cycle); DisposeQueue (Q); /* Free the memory */ Application of directed acyclic graph Topological Sort79Application of directed acyclic graph Topological Sortproject algo7-4 display this with Stack80 The result for algo7-4 81Application of directed acyclic graph Critical path a
72、nalysisAOE (Activity on Edge)Vertex：represents an event or a status;Edge: represents an activity. An edge (v, w) means that event v must be done before w may begin.Weight: Duration time of an activity. V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=482There is only one vertex whose i
73、ndegree is 0, and only one vertex whose outdegree is 0.No cycle.This type of a graph could be (and frequently) used to model projects.V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Application of directed acyclic graph Critical path analysis83QUESTIONSWhat is the earliest completion
74、 time for the project? -the longest path.Which activities can be delayed, and by how long, without affecting the minimum completion time? -not critical activities.V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Application of directed acyclic graph Critical path analysis84V4V1V3V8V2V
75、7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4e(i): earliest start time of ai.l(i): latest start time of ai (without affecting the minimum completion time) e(i)=l(i): ai is a critical activity, all the activities on the critical path are critical activities.ve(j): the earliest occurring time
76、of vjvl(j): the latest occurring time of vj (without affecting the minimum completion time)Application of directed acyclic graph Critical path analysis85If ai is represented by , its duration time is dut(), then e(i) = ve(j) l(i) = vl(k) - dut()VjVkaiV4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=
77、7a9=4a10=2a11=4Application of directed acyclic graph Critical path analysis86Calculate ve(j) and vl(j) first:(1) From ve(0)=0: ve(j) = maxve(i) + dut() i(2) vl(n-1)=ve(n-1), from the last one: vl(i) = minvl(j) - dut() jViVjaiViVjaiV4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Appli
78、cation of directed acyclic graph Critical path analysis87V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Application of directed acyclic graph Critical path analysis88V1V8V2V7V9V5a1=6a4=1a7=9a8=7a10=2a11=4Completion time is 18Two critical paths:(V1,V2,V5,V7,V9), (V1,V2,V5,V8,V9)Criti
79、cal acitivies: a1, a4, a7, a8, a10, a11Application of directed acyclic graph Critical path analysisSee project algo7-589Result for project algo7-590Application of directed acyclic graph Critical path analysisAlgorithm Analysis: Suppose there are n events and e activities in AOE： For Topological Sort
80、 ：Time Complexity O(n+e) ； For calculating the values of ve and vl, the Time Complexity is O(n+e) ； Based on the values of ve and vl, to fine the critical activities, the Time Complexity is O(n+e) ； SO, the Time Complexity of whole algorithm is O(n+e) 91Shortest PathRouting problems: find an optimal
81、 path in a networka shortest path in a graph or a digraph a cheapest path in a weighted graph or digraph Consider a directed graph that models an airline network vertices represent cities; directed arcs represent flights connecting these cities.Find the most direct route between two cities, that is,
82、 the route with the fewest intermediate stops. Equivalent to finding the length of a shortest path, one composed of a minimum number of arcs, from a start vertex to a destination vertex. 92Shortest Paths ProblemsInput: A graph with weights or costs associated with each edge.Output: The list of edges
83、 forming the shortest path.Sample problems:Find shortest path between two named verticesFind shortest path between two named verticesFind shortest path from Find shortest path from S S to all other vertices to all other vertices Single-Source Shortest PathsSingle-Source Shortest PathsFind shortest p
84、ath between all pairs of verticesFind shortest path between all pairs of vertices All-Pairs Shortest PathsAll-Pairs Shortest Paths Will actually calculate only distances.93Single-Source Shortest PathsGiven start vertex s, find the shortest path from s to all other vertices.Try 1: Visit vertices in s
85、ome order, compute shortest paths for all vertices seen so far, then add shortest path to next vertex x.Problem: Shortest path to a vertex already processed might go through x.Solution: Process vertices in order of distance from s.94Dijkstra IdeaCalculatedistancesinnon-decreasingorder: Allvertexesar
86、edividedinto 2groups：S：the vertexes that have found the shortest path from V0 to them. V-S=T：the vertexes that have not calculated the distances. AddingvertexinTtoSinnon-decreasingorderofdistances.the distances from V0 to vertexes in S not longer than the distances from V0 to any vertexes in TSee pr
87、oject algo7-695 For G(V,E) is expressed in Adjacency Matrix (1) Initially, S=v0; A array Dn to store the distance and Di is the shortest distance from v0 to vi:If exist edge (v0,vi )，Di = w(v0,vi ) ；If there is no such edge, then Di= + . (2) Select the minimal Dj from V-S, then vertex v vj j is the
88、destination of the currently shortest path, and Dj is the shortest distance. (3) Adding vj to S，and for all vertexes vi V-S， if Dj+arcsjkDk then Dk=Dj+arcsjk (4) Repeat processing (2),(3), until all vertexes are added into S.Dijkstra Algorithm96V1V3V2V5V46060100100V0202030301010505010105 5Step0： Ini
89、tializing，Dk is the edges from source V0 to Vk9697V1V3V2V5V46060100100V0202030301010505010105 5Step1：Select shortest path (v0,v2)，Add v2 to S9798V1V3V2V5V46060100100V0202030301010505010105 5Step2：Update the shortest path from v0 to v1、v3、v4、v5 .9899V1V3V2V5V46060100100V0202030301010505010105 5Step3：
90、Select shortest Path (v0,v4)，Add v4 to S99100V1V3V2V5V46060100100V0202030301010505010105 5Step4：Update shortest path from v0 to v1、v3、v5100101V1V3V2V5V46060100100V0202030301010505010105 5Step5：Select shortest path (v0,v4,v3)， Add v3 to S101102V1V3V2V5V46060100100V0202030301010505010105 5Step6：Update
91、 the shortest path from v0 to v1、v5 102103V1V3V2V5V46060100100V0202030301010505010105 5Step7：Select shortest path (v0,v4,v3, v5)， add v5 to S103104V1V3V2V46060100100V0202030301010505010105 5Step8：No path between v0 to v1，the path length is 。104V5typedef int PathMatrixMAXMAX;typedef int ShortPathTabl
92、eMAX;void ShortestPath(MGraph G, int v0, PathMatrix &P, ShortPathTable &D)/ 求图求图G从从v0到其余顶点到其余顶点v的最短路径的最短路径Pv和路径长度和路径长度Dv， / 如果如果Pvw为为TRUE，则则w为为v0到到v的最短路径上的顶点。的最短路径上的顶点。 for( v=0; vG.vexnum; v+) /初始化初始化 finalv = FALSE; / 表示顶点表示顶点v S Dv = G.Edgev0v; for( w=0; wG.vexnum; w+) Pvw = FALSE; if( Dv ) Pvv0
93、= TRUE; Pvv = TURE; Dv0 = 0; finalv0 = TRUE;105106 for( i=1; iG.vexnum; i+) /主循环，每次求一个主循环，每次求一个v到到v0的最短路径的最短路径 min = ; for( w=0; wG.vexnum; w+) / 求当前的最短路径的终点求当前的最短路径的终点v if( !finalw) if( Dw min ) v = w; min = Dw; finalv = TRUE; / 将顶点将顶点v加入加入S for( w=0; wG.vexnum; w+) / 更新当前的最短路径及长度更新当前的最短路径及长度 if( !
94、finalw & (min+G.EdgevwDw ) Dw = min+G.Edgevw; for(j=0; jG.vexnum; j+) Pwj = Pvj; Pww = TURE; 106107 All-Pairs Shortest PathsFor Dijkstras Algorithm, the Time complexity is O(n2)For every vertex u, v V, calculate d(u, v). Could run Dijkstras Algorithm |V| times.Better is Floyds Algorithm.Define a k-p
95、ath from u to v to be any path whose intermediate vertices all have indices less than k.108ExampleACB2643110 4 116 0 23 0InitialPath：AB ACBA BCCA0 4 116 0 23 7 0Add A:Path：AB ACBA BCCA CAB0 4 66 0 23 7 0Add B:Path：AB ABCBA BCCA CAB0 4 65 0 23 7 0Add C:Path：AB ABCBCA CA CABBCSee project algo7-7 Floyd algorithm109
