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

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

admin2014-12-25  81
问题 对于一个使用邻接表存储的有向图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)