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

9/8/2023数据结构与程序设计1数据结构与程序设计数据结构与程序设计(32)9/8/2023数据结构与程序设计2Chapter 12nGRAPHSnTopological SortnShortest PathnMinimal Spanning Trees9/8/2023数据结构与程序设计3Topological 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.79/8/2023数据结构与程序设计4Example:Topological order(拓扑排序)nC0 高等数学，C1 程序设计语言，C2 离散数学，C3 数据结构，C4 算法语言，C5 编译技术，C6 操作系统，C7 概率论，C8 计算机原理9/8/2023数据结构与程序设计512.4.2 Depth-first AlgorithmnStart by finding a vertex that has no successors 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.9/8/2023数据结构与程序设计69/8/2023数据结构与程序设计7Digraph Class,Topological Sorttypedef int Vertex;template class Digraph 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);9/8/2023数据结构与程序设计8Depth-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 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);9/8/2023数据结构与程序设计9Depth-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 added 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 successors of w.recursive_depth_sort(w,visited,topological_order);topological_order.insert(0,v);/Put v into topological_order.9/8/2023数据结构与程序设计1012.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.nApply the fact that every vertex must come before its successors.9/8/2023数据结构与程序设计119/8/2023数据结构与程序设计12Breadth-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 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+)neighborsv.retrieve(i,w);/Loop over all edges v-w.predecessor_countw+;9/8/2023数据结构与程序设计13Breadth-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_order.insert(topological order.size(),v);for(int j=0;j 0node from node V0 to other nodesV1V2V3V4bestdistance table9/8/2023数据结构与程序设计17Example Dijkstra AlgorithmnGreedy AlgorithmnAssume all weight of edge 0node from node V0 to other nodesV15V23V3 V42bestV4distance table9/8/2023数据结构与程序设计18Example Dijkstra Algorithmnstep 1:find the shortest path to node 0nnode 4 is selected to set Snode from node V0 to other nodesV15V23V3 V42bestV4distance table9/8/2023数据结构与程序设计19Example Dijkstra Algorithmnstep 2:recalculate the path to all other nodesnfind the shortest path to node 0.Node 2 is selectednode from node V0 to other nodesV155V233V3 6V42bestV4V2distance table9/8/2023数据结构与程序设计20Example 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 table9/8/2023数据结构与程序设计21Example 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 655V42bestV4V2V1V39/8/2023数据结构与程序设计22A Greedy Algorithm:Shortest Paths p587template 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/8/2023数据结构与程序设计23A Greedy Algorithm:Shortest Pathstemplate void Digraph:set_distances(Vertex source,Weight distance)const/*Post:The array distance gives the minimal path weight from vertex so