数据结构与程序设计(王丽苹)32-graphs拓扑排序.ppt

9/11/2023,数据结构与程序设计,1,数据结构与程序设计(32),王丽苹,9/11/2023,数据结构与程序设计,2,Chapter 12,GRAPHSTopological SortShortest PathMinimal Spanning Trees,9/11/2023,数据结构与程序设计,3,Topological 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 edge from v to w,then v precedes w in the sequential listing.P580 Figure 12.7,9/11/2023,数据结构与程序设计,4,Example:Topological order(拓扑排序),C0 高等数学，C1 程序设计语言，C2 离散数学，C3 数据结构，C4 算法语言，C5 编译技术，C6 操作系统，C7 概率论，C8 计算机原理,9/11/2023,数据结构与程序设计,5,12.4.2 Depth-first Algorithm,Start by finding a vertex that has no successors and place it last in the order.By 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.,9/11/2023,数据结构与程序设计,6,9/11/2023,数据结构与程序设计,7,Digraph Class,Topological Sort,typedef int Vertex;template class Digraph public:Digraph();void read();void write();/methods to do a topological sortvoid depth_sort(List,9/11/2023,数据结构与程序设计,8,Depth-First Algorithm p581,template void Digraph:depth_sort(List,9/11/2023,数据结构与程序设计,9,Depth-First Algorithm p581,template void Digraph:recursive_depth_sort(Vertex v,bool*visited,List/Put v into topological_order.,9/11/2023,数据结构与程序设计,10,12.4.3 Breadth-First Algorithm,Start by finding the vertices that should be first in the topological order.That is the vertices which have no predecessor.Apply the fact that every vertex must come before its successors.,9/11/2023,数据结构与程序设计,11,9/11/2023,数据结构与程序设计,12,Breadth-First Algorithm p582,template void Digraph:breadth_sort(List,9/11/2023,数据结构与程序设计,13,Breadth-First Algorithm p582,Queue 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_order.insert(topological order.size(),v);for(int j=0;j neighborsv.size();j+)neighborsv.retrieve(j,w);/Traverse successors of v.predecessor_countw;if(predecessor_countw=0)ready_to_process.append(w);ready_to_process.serve();,9/11/2023,数据结构与程序设计,14,12.5 A Greedy Algorithm:Shortest Paths,The problem of shortest paths:Given a directed graph in which each edge has a nonnegativeweight or cost,find a path of least total weight from a givenvertex,called the source,to every other vertex in the graph.P583 figure 12.8,9/11/2023,数据结构与程序设计,15,Method for shortest path:Dijkstra Algorithm（Greedy Algorithm）,Method:We keep a set S of vertices whose shortest distances from source is known.At each step,we add to S a remaining vertex for which the shortest path from source has been found.We maintain a table distance that gives,for each remaining vertex v,the shortest distance from S to v.Initial:S=source,distance table is the distance from source to v.,9/11/2023,数据结构与程序设计,16,Example Dijkstra Algorithm,Greedy AlgorithmAssume all weight of edge 0,distance table,9/11/2023,数据结构与程序设计,17,Example Dijkstra Algorithm,Greedy AlgorithmAssume all weight of edge 0,distance table,9/11/2023,数据结构与程序设计,18,Example Dijkstra Algorithm,step 1:find the shortest path to node 0node 4 is selected to set S,distance table,9/11/2023,数据结构与程序设计,19,Example Dijkstra Algorithm,step 2:recalculate the path to all other nodesfind the shortest path to node 0.Node 2 is selected,distance table,9/11/2023,数据结构与程序设计,20,Example Dijkstra Algorithm,step 3:recalculate the path to all other nodesfind the shortest path to node 0.node 1 is selected,distance table,9/11/2023,数据结构与程序设计,21,Example Dijkstra Algorithm,step 4:recalculate the path to all other nodesfind the shortest path to node 0.node 3 is selected,9/11/2023,数据结构与程序设计,22,A Greedy Algorithm:Shortest Paths p587,template class Digraph public:/Add a constructor and methods for Digraph input and output.void set_distances(Vertex source,Weight distance)const;protected:int count;Weight adjacencygraph_sizegraph_size;,9/11/2023,数据结构与程序设计,23,A Greedy Algorithm:Shortest Paths,template void Digraph:set_distances(Vertex source,Weight distance)const/*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 S.distancesource=0;,9/11/2023,数据结构与程序设计,24,A Greedy Algorithm:Shortest Paths,for(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(min+adjacencyvw distancew)distancew=min+adjacencyvw;,9/11/2023,数据结构与程序设计,25,12.6 Minimal Spanning Trees（MST）最小生成树,A(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.If original graph has n vertices,the spanning tree has n vertices and n-1 edges.No circle in this subgraphDEFINITION 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.,9/11/2023,数据结构与程序设计,26,Two Spanning Tree,9/11/2023,数据结构与程序设计,27,Minimum Spanning Tree(MST),6,7,1,5,10,20,Spanning tree with minimum weight,9/11/2023,数据结构与程序设计,28,Prims Algorithm for Minimal Spanning Trees,Start with a source vertex.Keep a set X of those vertices whose paths to source in the minimal spanning tree that we are building have been found.Keep the set Y of edges that link the vertices in X in the tree under construction.The vertices in X and edges in Y make up a small tree that grows to become our final spanning tree.,9/11/2023,数据结构与程序设计,29,Prims Algorithm for Minimal Spanning Trees,Initially:source is the only vertex in X,and Y is empty.At each step:we add an additional vertex to X:This vertex is chosen so that an edge back to X has samllest weight.This minimal edge back to X is added to Y.neighborw,is a vertex in X which is nearest to w.Distancew,is the value for the nearst distance of w.,9/11/2023,数据结构与程序设计,30,Example of Prims Algorithm,9/11/2023,数据结构与程序设计,31,Example of Prims Algorithm,9/11/2023,数据结构与程序设计,32,Example of Prims Algorithm,9/11/2023,数据结构与程序设计,33,Example of Prims Algorithm,9/11/2023,数据结构与程序设计,34,Implementation of Prims Algorithm,template class Network:public Digraph public:Network();void read();/overridden method to enter a Networkvoid make empty(int size=0);void add edge(Vertex v,Vertex w,Weight x);void minimal spanning(Vertex source,Network,9/11/2023,数据结构与程序设计,35,template void Network:minimal spanning(Vertex source,Network/source alone is in the set X.,9/11/2023,数据结构与程序设计,36,for(int i=1;i count;i+)Vertex v;/Add one vertex v to X on each pass.Weight min=innity;for(w=0;w count;w+)if(!componentw)if(distancew min)v=w;min=distancew;if(min innity)componentv=true;tree.add edge(v,neighborv,distancev);for(w=0;w count;w+)if(!componentw)if(adjacencyvw distancew)distancew=adjacencyvw;neighborw=v;else break;/finished a component in disconnected graph,9/11/2023,数据结构与程序设计,37,The End Thank you！,