以下哪些算法可以检测一个有向图中是否存在环( )
无向图,若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边),则该无向图必定存在环路。 参考图的关节点与重连通分量,图的深度优先生成树。 使用拓扑排序可以判断一个无向图中是否存在环,具体步骤如下: 求出图中所有结点的度。 将所有度 <= 1 的结点入队。(独立结点的度为 0) 当队列不空时,弹出队首元素,把与队首元素相邻节点的度减一。 如果相邻节点的度变为一,则将相邻结点入队。 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过,无环; 反之,则有环 //////////////////////////////////////////////////////////////////////// 有向图判断是否存在环 对于有向图,利用拓扑排序来判断是否存在环: 对于无环的有向图,对其进行拓扑排序可输出其所有顶点,而有环的图则不行! //////////////////////////////////////////////////////////////////////// 使用拓扑排序判断无向图和有向图中是否存在环的区别在于: 在判断无向图中是否存在环时,是将所有度 <= 1 的结点入队; 在判断有向图中是否存在环时,是将所有入度 = 0 的结点入队 //////////////////////////////////////////////////////////////////////// 关键路径虽然不允许有环 在求关键路径时如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n,则说明网中有环, 不能求出关键路径,算法结束。 且是在无向图中才有解。 求解关键路径问题,必须是有向无环图才有关键路径。