数据结构与程序设计(32)-Graphs 拓扑排序

1、11/23/2021数据结构与程序设计1Chapter 12nGRAPHSnTopological SortnShortest PathnMinimal Spanning Trees11/23/2021数据结构与程序设计2Topological order(拓扑排序)Let G be a directed graph with no cycles. A topological order for G is a sequential listing of all the vertices in G such that, for all vertices v,w G, if there is an

2、 edge from v to w, then v precedes w in the sequential listing.P580 Figure 12.711/23/2021数据结构与程序设计3Example: Topological order(拓扑排序)nC0 高等数学，C1 程序设计语言，C2 离散数学， C3 数据结构，C4 算法语言，C5 编译技术，C6 操作系统， C7 概率论，C8 计算机原理11/23/2021数据结构与程序设计412.4.2 Depth-first AlgorithmnStart by finding a vertex that has no succes

3、sors and place it last in the order.nBy recursive, After placed all the successors of a vertex into the topological order, then place the vertex itself in position before any of its successors.11/23/2021数据结构与程序设计511/23/2021数据结构与程序设计6Digraph Class, Topological Sorttypedef int Vertex;template class Di

4、graph public:Digraph( );void read( );void write( );/ methods to do a topological sortvoid depth_sort(List &topological_order);void breadth_sort(List &topological_order);private:int count;List neighborsgraph_size;void recursive_depth_sort(Vertex v, bool visited, List &topological_order);1

5、1/23/2021数据结构与程序设计7Depth-First Algorithm p581template void Digraph :depth_sort(List &topological_order)/* Post: The vertices of the Digraph are placed into List topological_order with adepth-first traversal of those vertices that do not belong to a cycle.Uses: Methods of class List, and function

6、 recursive_depth_sort to perform depth-first traversal. */bool visitedgraph_size;Vertex v;for (v = 0; v count; v+) visitedv = false;topological_order.clear( );for (v = 0; v count; v+)if (!visitedv) / Add v and its successors into topological order.recursive_depth_sort(v, visited, topological_order);

7、11/23/2021数据结构与程序设计8Depth-First Algorithm p581template void Digraph :recursive_depth_sort(Vertex v, bool *visited, List &topological_order)/* Pre: Vertex v of the Digraph does not belong to the partially completed List topological_order.Post: All the successors of v and finally v itself are adde

8、d to topological orderwith a depth-first search.Uses: Methods of class List and the function recursive_depth_sort. */ visitedv = true;int degree = neighborsv.size( );for (int i = 0; i degree; i+) Vertex w; / A (neighboring) successor of vneighborsv.retrieve(i, w);if (!visitedw) / Order the successor

9、s of w.recursive_depth_sort(w, visited, topological_order);topological_order.insert(0, v); / Put v into topological_order.11/23/2021数据结构与程序设计912.4.3 Breadth-First AlgorithmnStart by finding the vertices that should be first in the topological order. That is the vertices which have no predecessor.nAp

10、ply the fact that every vertex must come before its successors.11/23/2021数据结构与程序设计1011/23/2021数据结构与程序设计11Breadth-First Algorithm p582template void Digraph :breadth_sort(List &topological_order)/* Post: The vertices of the Digraph are arranged into the List topological_orderwhich is found with a

11、breadth-first traversal of those vertices that do not belongto a cycle.Uses: Methods of classes Queue and List. */ topological_order.clear( );Vertex v, w;int predecessor_countgraph size;for (v = 0; v count; v+) predecessor_countv = 0;for (v = 0; v count; v+)for (int i = 0; i neighborsv.size( ); i+)

12、neighborsv.retrieve(i, w); / Loop over all edges v-w.predecessor_countw+;11/23/2021数据结构与程序设计12Breadth-First Algorithm p582Queue ready_to_process;for (v = 0; v count; v+)if (predecessor_countv = 0)ready_to_process.append(v);while (!ready_to_process.empty( ) ready_to_process.retrieve(v);topological_or

13、der.insert(topological order.size( ), v);for (int j = 0; j 0node from node V0 to other nodesV1V2V3V4bestdistance table11/23/2021数据结构与程序设计16Example Dijkstra AlgorithmnGreedy AlgorithmnAssume all weight of edge 0node from node V0 to other nodesV15V23V3 V42bestV4distance table11/23/2021数据结构与程序设计17Examp

14、le Dijkstra Algorithmnstep 1: find the shortest path to node 0nnode 4 is selected to set Snode from node V0 to other nodesV15V23V3 V42bestV4distance table11/23/2021数据结构与程序设计18Example Dijkstra Algorithmnstep 2: recalculate the path to all other nodesnfind the shortest path to node 0. Node 2 is select

15、ednode from node V0 to other nodesV155V233V3 6V42bestV4V2distance table11/23/2021数据结构与程序设计19Example Dijkstra Algorithmnstep 3: recalculate the path to all other nodesnfind the shortest path to node 0. node 1 is selectednode from node V0 to other nodesV1554V233V3 65V42bestV4V2V1distance table11/23/20

16、21数据结构与程序设计20Example Dijkstra Algorithmnstep 4: recalculate the path to all other nodesnfind the shortest path to node 0. node 3 is selectednode from node V0 to other nodesV1554V233V3 655V42bestV4V2V1V311/23/2021数据结构与程序设计21A Greedy Algorithm: Shortest Paths p587template class Digraph public: / Add a

17、 constructor and methods for Digraph input and output.void set_distances(Vertex source, Weight distance) const;protected:int count;Weight adjacencygraph_sizegraph_size;11/23/2021数据结构与程序设计22A Greedy Algorithm: Shortest Pathstemplate void Digraph : set_distances(Vertex source,Weight distance) const/*

18、Post: The array distance gives the minimal path weight from vertex source to each vertex of the Digraph. */ Vertex v, w;bool foundgraph_size; / Vertices found in Sfor (v = 0; v count; v+) foundv = false;distancev = adjacencysourcev;foundsource = true; / Initialize with vertex source alone in the set

19、 S.distancesource = 0;11/23/2021数据结构与程序设计23A Greedy Algorithm: Shortest Pathsfor (int i = 0; i count; i+) / Add one vertex v to S on each pass.Weight min = infinity;for (w = 0; w count; w+) if (!foundw)if (distancew min) v = w;min = distancew;foundv = true;for (w = 0; w count; w+) if (!foundw)if (mi

20、n + adjacencyvw distancew)distancew = min + adjacencyvw;11/23/2021数据结构与程序设计2412.6 Minimal Spanning Trees（MST）最小生成树nA (connected) tree that is build up out of all the vertices and some of the edges of G is called a spanning tree of G.nIf original graph has n vertices, the spanning tree has n vertices

21、 and n-1 edges.nNo circle in this subgraphnDEFINITION A minimal spanning tree of a connected network is a spanning tree such that the sum of the weights of its edges is as small as possible.11/23/2021数据结构与程序设计25Two Spanning Tree11/23/2021数据结构与程序设计26Minimum Spanning Tree (MST)6715102061015Spanning tr

22、ee with minimum weight11/23/2021数据结构与程序设计27Prims Algorithm for Minimal Spanning TreesnStart with a source vertex. nKeep a set X of those vertices whose paths to source in the minimal spanning tree that we are building have been found. nKeep the set Y of edges that link the vertices in X in the tree

23、under construction. nThe vertices in X and edges in Y make up a small tree that grows to become our final spanning tree.11/23/2021数据结构与程序设计28Prims Algorithm for Minimal Spanning TreesnInitially:nsource is the only vertex in X, and Y is empty. nAt each step:nwe add an additional vertex to X: nThis ve

24、rtex is chosen so that an edge back to X has samllest weight. This minimal edge back to X is added to Y .nneighborw, is a vertex in X which is nearest to w.nDistancew, is the value for the nearst distance of w. 11/23/2021数据结构与程序设计29Example of Prims Algorithm11/23/2021数据结构与程序设计30Example of Prims Algo

25、rithm11/23/2021数据结构与程序设计31Example of Prims Algorithm11/23/2021数据结构与程序设计32Example of Prims Algorithm11/23/2021数据结构与程序设计33Implementation of Prims Algorithmtemplate class Network: public Digraph public:Network( );void read( ); / overridden method to enter a Networkvoid make empty(int size = 0);void add

26、 edge(Vertex v, Vertex w, Weight x);void minimal spanning(Vertex source,Network &tree) const;11/23/2021数据结构与程序设计34template void Network : minimal spanning(Vertex source, Network &tree) const/* Post: The Network tree contains a minimal spanning tree for the connected componentof the original Network