利用DFS实现无环图拓扑排序
·
对于有向无环图的任意节点u，v，它们之间的关系必然是祖先与子孙节点或者其他关系
若节点u是v的祖先，则在调用DFS访问u的过程中，必然会递归访问v，并且v的DFS函数结束时间早于u的DFS函数结束时间。若u是v的子孙，则v的结束时间一定大于u的结束时间。若是其他关系则在拓扑排序中的顺序随意。
则可以考虑在DFS调用的过程中设定一个时间标记，在DFS调用结束时，对各个节点计时，祖先节点的结束时间必然大于子孙节点的结束时间。从而按照结束时间排序，可以得到一个拓扑排序。
bool visited[MAX_SIZE];
int finishTime[MAX_SIZE];
void DFSTraverse(Graph G){
for(v=0;v<G.vexNum;v++){
visited[v]=false;
}
int time=0;
for(v=0;v<G.vexNum;v++){
if(!visited[v]){
DFS(G,v);
}
void DFS(Graph G,int v){
visited[v]=true;
visit(v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]){
DFS(G,w);
}
}
time=time+1;
finishTime[v]=time;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)