校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 图的遍历
题目

以下哪些算法可以检测一个有向图中是否存在环( )

A.深度优先遍历

B.广度优先遍历

C.拓扑排序

D.关键路径算法

解答

正确答案是 AC

简单说一下算法步骤,为什么选DFS和拓扑排序:

DFS的时候,如果要访问的元素已经访问过,它在当前的栈内还没出栈,那么就是有环。BFS不行是因为可能有多个节点指向该节点,不一定是因为有环。

拓扑排序会循环执行以下两步:
(1) 选择一个入度为0的顶点,输出
(2) 从图中删除此顶点以及所有的出边

循环结束后,若输出的顶点数小于网中的顶点数,则说明有回路

C 0条回复 评论

帖子还没人回复快来抢沙发