判断有向图是否存在回路

判断有向图是否存在回路可以使用拓扑排序算法。拓扑排序算法可以将有向无环图（DAG）中的节点线性排序，使得对于任何一条有向边（u,v），节点u在排序中都排在节点v的前面。如果有向图中存在回路，那么无法进行拓扑排序。

具体做法如下：

1. 统计每个节点的入度（指向该节点的边的数量），并将入度为0的节点加入队列。

2. 从队列中弹出一个节点，并将其从图中删除。同时，将它所有指向的节点的入度减1。如果有节点的入度变为0，将其加入队列。

3. 重复步骤2，直到队列为空。如果图中还存在节点，但是无法将入度为0的节点加入队列，说明图中存在回路。

如果存在回路，说明存在一个节点可以通过若干条有向边回到自身，因此这个节点的入度永远不会为0。因此，如果在进行拓扑排序的过程中，无法找到入度为0的节点，就可以判断出有向图中存在回路。

相关问题

c++用邻接矩阵判断有向图是否存在回路

使用邻接矩阵来判断有向图是否存在回路的方法如下：

1. 首先，创建一个大小为n×n的邻接矩阵，其中n表示图的顶点数量。初始时，所有矩阵元素值设为0。

2. 将有向图的边按照起始顶点和终止顶点的关系填入邻接矩阵中。如果存在从顶点i到顶点j的边，则将矩阵元素M[i][j]设为1。

3. 对于每个顶点v，从它的下一个顶点w开始进行深度优先搜索（DFS）。如果w已被访问过且不为v，则表示存在回路。若没有回路，则进行下一步。

4. 对于每个顶点v，如果DFS中搜索到它自身，则表示存在回路。若没有回路，则进行下一步。

5. 如果上述两步都没有找到回路，则判断无向图存在回路。若存在回路，则返回"有回路"，否则返回"无回路"。

通过邻接矩阵判断有向图是否存在回路的时间复杂度为O(n^2)，其中n表示图的顶点数量。因为需要遍历邻接矩阵的所有元素，并进行DFS。但是，通过使用一些优化算法，如剪枝等技巧，可以降低时间复杂度。

1076: 判断给定有向图是否存在回路

判断给定有向图是否存在回路，可以使用拓扑排序或深度优先搜索算法。如果在拓扑排序中发现有节点的入度为，但是该节点的出边指向的节点已经被访问过，那么就说明存在回路。如果使用深度优先搜索，如果在搜索过程中遇到了已经访问过但是还没有回溯的节点，那么就说明存在回路。