数据结构teachingmaterials7.ppt

Application using graphs themselves as data structures 2. Topological Sorting / 拓扑排序 实现算法: 假设用混合模式的存储结构，且产生的拓扑排序结果序列为 Vertex toporder[MaxVertex]; /*DepthTopSort: generate depth-first topological order Pre: G is a directed graph with no cycles implemented with a contiguous list of vertices and linked adjacency lists. Post: The function makes a depth-first traversal of G and generates the resulting topological order in the array T. Uses: RecDepthSort performs the recursive depth-first traversal. */ void DepthTopSort ( Graph *G, Toporder T ) { Vertex v; //next vertex whose successors are to be ordered int place; //next position in the topological order to be filled for ( v = 0; v G-n; v++ ) visited[v] = FALSE; place = G-n-1; for ( v = 0; v G-n; v++ ) if ( !visited[v] ) RecDepthSort(G, v, place, T); } //Breadth-First Algorithm to be wished to consider after class … to be continued 算法分析: 时间复杂性为O(n+e). Application using graphs themselves as data structures 2. Topological Sorting / 拓扑排序 实现算法: 假设用混合模式的存储结构，且产生的拓扑排序结果序列为 Vertex toporder[MaxVertex]; /* RecDepthSort: performs the recursion for DepthTopSort Pre: v is a vertex of the graph G and places is the next location in the topological order T to be determined (starting from the end of the final ordered list). Post: The procedure puts all the successors of v and finally v itself into the toplogical order T in depth-first order. Uses: Global array visited and RecDepthSort recursively. */ void RecDepthSort ( Graph *G, int v, int *place, Toporder T ) { Vertex curvertex; //vertex adjacent to v Edge *curedge; //traverses list of vertices adjacent to v visited[v] = TRUE; while ( curedge ) { curvertex = curedge-endpoint; //find the first vertex succeeding to v if ( !visited[curvertex] ) RecDepthSort[G, Curvertex, place, T); //order the successors of curvertex curedge=curedge-nextedge; } //go on to next immediate suc