怎么判断有向图是否有环

判断有向图是否有环可以使用拓扑排序算法。具体步骤如下：

1. 统计每个节点的入度，入度为0的节点入队。

2. 从队列中取出一个节点，将其所有邻接节点的入度减1。

3. 如果邻接节点的入度为0，则将其加入队列。

4. 重复2、3步骤，直到队列为空。

5. 判断拓扑排序结果中节点的个数是否等于图中节点的个数。如果不等，则说明图中存在环。

如果拓扑排序结束后，所有节点都被遍历了，则说明该有向图无环。否则，存在未被遍历的节点，即存在环。

相关问题

如何判断有向图是否有环

要判断一个有向图是否有环，可以使用拓扑排序算法或强连通分量算法。

拓扑排序算法是一种基于有向图的算法，它可以用来确定一个有向无环图（DAG）的顶点的线性排序。如果一个有向图存在环，则无法进行拓扑排序，因为环中的顶点无法确定其相对顺序。因此，如果利用拓扑排序算法求环，并且最后剩余的点不是环中的顶点，那么该有向图存在环。

强连通分量算法是另一种判断有向图中是否存在环的方法。根据强连通分量的定义，如果从顶点i到j有一条路径，并且从j到i也有一条路径，那么i和j就属于同一个强连通分量。而强连通分量中必定存在环。因此，如果使用强连通分量算法，如果存在至少一个强连通分量，那么该有向图存在环。

综上所述，要判断有向图是否有环，可以使用拓扑排序算法或强连通分量算法。如果最后剩余的点中存在非环中的顶点，或者存在至少一个强连通分量，则该有向图存在环。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>

DFS判断有向图是否有环

DFS（深度优先搜索）可以用来判断有向图是否有环。

具体步骤如下：

1. 选择一个起点，从该点开始进行深度优先搜索。

2. 每次访问一个未访问过的节点时，将其标记为“已访问”。

3. 每次遍历到一个节点时，判断该节点的所有邻居节点是否已经被访问过。

4. 如果邻居节点已经被访问过，且不是当前节点的父节点，则说明有环。

5. 如果邻居节点未被访问过，则以该节点为起点，重复步骤2-4。

6. 如果所有节点都被访问过，且没有发现环，则说明该有向图无环。

具体实现可以使用递归或栈来实现。