數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(32)-Graphs 拓撲排序

1、11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計1Chapter 12nGRAPHSnTopological SortnShortest PathnMinimal Spanning Trees11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計3Example: Topological order(拓撲排序)nC0 高等數(shù)學(xué)，C1 程序設(shè)計語言，C2 離散數(shù)學(xué)， C3 數(shù)據(jù)結(jié)構(gòu)，C4 算法語言，C5 編譯技術(shù)，C6 操作系統(tǒng)， C7 概率論，C8 計算機原理11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計511/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計1011/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計16Example Dijkstra AlgorithmnGreedy AlgorithmnAssume all weight of edge 0node from node V0 to other nodesV15V23V3 V42bestV4distance table11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計25Two Spanning Tree11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計26Minimum Spanning Tree (MST)6715102061015Spanning tr

22、ee with minimum weight11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計29Example of Prims Algorithm11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計30Example of Prims Algo

25、rithm11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計31Example of Prims Algorithm11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計32Example of Prims Algorithm11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計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