考点
数据结构-图-图的遍历
面5笔5下面哪一方法可以判断出一个有向图是否有环（回路）：（）
A.深度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
前往“校大”小程序，刷题更快
最新校招难题刷题，快来进刷题群吧
解答
正确答案是 A B
对于有向图的拓扑排序,
1计算图中所有点的入度，把入度为0的点加入栈
2.如果栈非空：取出栈顶顶点a，输出该顶点值，删除该顶点
3从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈
4如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列
