DFS拓扑排序函数头(针对回路) void Topsortby DFS_ Circle(Graph& G) ∥对图所有顶点的标志位进行初始化 for(int i=0; i<G.VerticesNum(; i++) G. Mark[]= UNVISITED int *result=new int[G. VerticesNum(] int tag= NOTCIRCLED, index=0; ∥对图的所有顶点进行处理 for(i=0; i<G. VerticesNum(; i++ if ((G. Mark[]== UNVISITED &&(tag== NOTCIRCLEDD) Do_ topsort Circle(G,i, result, index,tag);∥递归 if (tag == NOTCIRCLED) for(i=G. VerticesNum0-1; i>=0; i--) ∥逆序输出 Visit(G, result[])
DFS拓扑排序函数头（针对回路） void TopsortbyDFS_Circle(Graph& G) { //对图所有顶点的标志位进行初始化 for(int i=0; i<G.VerticesNum(); i++) G.Mark[i] = UNVISITED; int *result=new int[G.VerticesNum()]; int tag = NOTCIRCLED, index = 0; //对图的所有顶点进行处理 for (i=0; i<G.VerticesNum(); i++) if ((G.Mark[i] == UNVISITED) && (tag == NOTCIRCLED)) Do_topsort_Circle(G, i, result, index, tag); //递归 if (tag == NOTCIRCLED) for (i=G.VerticesNum()-1; i>=0; i--) //逆序输出 Visit(G, result[i]); }
DFS拓扑排序的递归主函数(回路) void Do topsort_ Circle(Graph& G, int V, int*result, int &index, int& tag) if (G. MarkMV== VISITED)i cout<<"此图有环!"<<endl; ∥图有环 tag CIRCLED; return; G, Mark[=ⅥsTED; for (Edge e=G. FirstEdge(v); GSeDge(e); e=G. NextEdge(e))t ∥访问v邻接到的所有未被访问过的顶点 if ((G. Mark[G. ToVertex(e)]= PUSHED) &&(tag==NOTCIRCLED) Do topsort_ Circle(G, G. Tovertex(e), result, index, tag) result[index++]V; G.Mark[V= PUSHED
DFS拓扑排序的递归主函数（回路） void Do_topsort_Circle(Graph& G, int V,int *result,int &index, int& tag) { if (G.Mark[V] == VISITED) { cout << "此图有环！"<< endl; //图有环 tag = CIRCLED; return; } G.Mark[V]= VISITED; for (Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e)) { //访问V邻接到的所有未被访问过的顶点 if ((G.Mark[G.ToVertex(e)] != PUSHED) && (tag == NOTCIRCLED) ) Do_topsort_Circle(G, G.ToVertex(e),result, index, tag); } result[index++]=V; G.Mark[V] = PUSHED; }
判断拓扑 例题 排序序列 是否唯 ■PoJ1094 已知A<B,A<C,B<c,c<D,B<D A,B,C,D的大小关系,可由前几个表达式确定?
例题 ◼ POJ 1094 – 已知A<B, A<C, B<C, C<D, B<D – A, B, C, D的大小关系，可由前几个表达式确定？ 判断拓扑 排序序列 是否唯一
拓扑排序应用 从第一个规则开始依次读入 如果有环,则报错 如果可以拓扑排序,则停止,输出结果
拓扑排序应用 ◼ 从第一个规则开始依次读入 – 如果 有环，则报错 – 如果 可以拓扑排序，则停止，输出结果
关键路径 ■研究问题: 完成整项工程至少需要多少时间? 哪些活动是影响整个工程进度的关键? 加权最长的路径 a 10 a 2 a a11 a2=5 2 V4) Ve
关键路径 ◼ 研究问题： – 完成整项工程至少需要多少时间？ – 哪些活动是影响整个工程进度的关键？ – 加权最长的路径 V4 V1 V3 V8 V2 V7 V9 V6 V5 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4