怎么判断有向图是否有环

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

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>

判断有向图是否有环的方法

判断有向图是否有环的方法有两种，分别是拓扑排序和深度优先搜索。

1. 拓扑排序：对于有向无环图（DAG），其拓扑排序是一种线性排序，可以用来判断是否有环。具体步骤如下：

- 从DAG中选择一个没有前驱（即入度为0）的顶点并输出；
- 从DAG中删除该顶点以及所有以它为起点的有向边；
- 重复1、2步，直到DAG为空或者不存在没有前驱的顶点为止。

如果在执行过程中，DAG中所有顶点都被输出，则DAG是有向无环图，否则存在环。

2. 深度优先搜索：对于一个有向图G，如果在深度优先搜索时，发现了一条边指向已经访问过的节点，则存在环。具体步骤如下：

- 从任意一个节点开始进行深度优先搜索；
- 对于每个节点，记录其状态，有三种状态：未访问、正在访问、已经访问；
- 对于每个节点进行深度优先搜索，如果在搜索的过程中遇到已经访问过的节点，则存在环，否则遍历结束。

两种方法的时间复杂度均为O(V+E)，其中V为节点数，E为边数。