对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序,写出在遍历图的同时进行拓扑排序的算法。

admin2014-12-25  59

问题 对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序,写出在遍历图的同时进行拓扑排序的算法。

选项

答案 int flag[];count=0;success=1; /*success:测试拓扑排序是否成功*/ InitQueue(Q); voidDFSTopSort(ALGraphG) { /*对以邻接表为存储结构的有向图G进行拓扑排序*/ for(v=0jVnextarc) if(visited[p->adjvex]&&flag[p一>adjvex]==0) /*DFS结束前出现回边*/ success=0; elseif(!visited[P一>adjvex]) {DFS(G,P一>adjvex);flaq[p一>adjvex]=1;} }

解析 对有向图进行深度优先搜索,可以判定图中是否有回路。若从有向图的某个顶点v出发深度优先遍历,在DFS(v)结束前,出现顶点n到顶点v的回边,图中必有环。用数组flag=1,表示其邻接点已全部被搜索完。由于深度优先搜索得到的序列是逆拓扑排序序列。因此用队列存放所访问的顶点。算法描述如下。
转载请注明原文地址:https://kaotiyun.com/show/qaVx777K
0

相关试题推荐
最新回复(0)