Python中检测有向图中的循环

在此问题中，我们将给定一个有向图。我们的任务是判断有向图是否包含构成环的路径。

让我们看一个有向图的例子

输入: V = 8, E = 9

1 → 2 → 3 → 4

â á á â

5 → 6 7 ß 8

输出： 是

在这个图中，似乎存在两个环。然而，只有一个环。节点 1、5、6 和 2 之间看似的环并不在同一条路径上。1 和 2 的路径方向不同。图中唯一的环是节点 3、4、8 和 7 形成的环。所有节点都在同一条路径上。

输入: N = 4, E = 4

1 → 2

â á

5 → 6

输出： 是

这个图没有任何环。

方法 - 1

首先，我们将使用深度优先搜索或 DFS 算法来解决这个问题。

与无向图的 DFS 算法不同，仅凭父节点无法判断是否存在环。原因是父节点应该在同一条路径上，而节点本身无法确认这一点。

例如，在这个图中：

1 → 2 → 3 → 4

â á á â

5 → 6 7 ß 8

节点 2 将被访问。第一次访问 2 时，其父节点为 1。第二次，通过节点 6 访问 2；6 的父节点是 5，不等于 2，这表明存在环。但是，2 和 1 和 6 不在同一条路径上。

因此，这里的主要问题在于路径。

为了维护路径检查，我们将创建另一个数组，该数组将记录当前节点是否已在当前路径中被访问。一旦路径完成，路径访问数组中的节点将使用回溯技术设置为 False 或 0。

这将确保只有当一个节点在同一条路径上被重新访问时，算法才会返回 True 表示存在环。如果访问的节点在不同的路径上，它们将不被视为环的一部分。

现在让我们看看这个算法。

算法

请按照以下步骤来实现这个想法

• 我们将创建两个函数，第一个是 detect(vis, path, src)，第二个是 isCyclic()。
• 其中，adj 是图的邻接列表，V 是图中的顶点数，vis 是用于记录已访问节点的数组，path 是用于记录特定路径的已访问节点的数组，src 是图的当前顶点。
• 我们将在 isCyclic() 函数中初始化 vis 和 path 数组，并将它们的值设置为 0。
• 我们将在 isCyclic() 函数中创建一个 for 循环。该循环将从 1 运行到 V。如果节点未被访问，将为该节点调用 detect() 函数。此循环将确保检查图的所有连通分量。
• 在 detect() 函数中，第一个任务是标记 src 节点为已访问和路径已访问。
• 然后，我们将遍历 src 节点的相邻节点。
• 如果相邻节点尚未被访问，我们将递归调用 detect 函数，并将当前相邻节点作为 src 节点传递。
• 但是，如果当前相邻节点已被访问，我们将检查该节点是否也已路径访问。如果该节点已路径访问，我们将返回 True。
• 在循环结束时，我们必须通过回溯将路径访问数组的节点标记为默认状态。因此，我们将 path[src] 标记为 0。这将确保当路径在递归堆栈出栈时结束，该路径的所有节点都被标记为未访问。
• 最后，如果路径在没有环的情况下结束，我们将返回 False。

下面是 DFS 算法的 Python 程序。

代码

输出

The graph has a cycle

方法 - 2

在此方法中，我们将使用 Kahn 算法来检测有向图中的环。我们将在此算法中使用 BFS 遍历。

Kahn 算法常用于拓扑排序。在拓扑排序中，我们将有向无环图的顶点从 A 排列到 B，以便 A 始终出现在 B 之前。实现 Kahn 算法的第一步是找到每个顶点的入度。入度是指指向目标顶点的边的数量。我们通过创建一个初始入度计数为 0 的数组来实现这一点。然后，我们将遍历邻接列表中的每条边，并为每个顶点增加入度计数。

入度为 0 的节点将从图中移除并添加到已排序列表中。然后，我们运行一个 while 循环，并将零入度的顶点添加到已排序列表中。

在 Kahn 算法中，第一步是找到所有不依赖于其他节点的节点。指向该节点的其他图节点数为零的节点被认为是零依赖。这些节点具有零入度。我们将从零入度节点开始执行 BFS 遍历。在 BFS 遍历的每次迭代中，我们将减少相邻节点的入度计数，并继续将零入度的节点添加到队列中。

为了可视化解决方案，我们可以将其理解为不断移除没有依赖的节点。这样，问题就会简化为一个更小的问题。图会不断变小，从而简化问题。但是，要消除一个节点，我们也必须更新其相邻节点的依赖性。我们将减少这些相邻节点的入度，并检查它们的依赖性是否减少到零。一旦所有零入度节点都被遍历，我们将检查是否还有具有大于零入度的节点。如果存在这样的节点，则表示图中包含环。

让我们来理解一下这个方法

• 第一步，我们将计算每个图顶点的入度。我们将已访问节点的计数初始化为 0。
• 一旦我们得到所有入度计数，我们将找到入度为零的顶点。我们将这些节点添加到 BFS 遍历的队列中。
• 我们将执行 BFS 遍历，并在每次迭代中减少入度。
• 计算 DAG 中每个顶点的入度（传入边的数量），并将已访问节点的计数设置为 0。
• 选择所有入度值为 0 的顶点，然后将它们全部入队。
• 从队列中移除一个顶点（出队操作）后，将已访问节点数加一。
• 对于其每个相邻节点或顶点，将入度减 1。
• 如果相邻节点或顶点的入度减至零，则将其添加到队列中。
• 重复步骤 3，直到队列为空。
• 如果已访问节点的数量不等于图的顶点数量，则提供的图的拓扑排序是不可能的。

说明

Graph 类已在以下代码中实现，并且图表示为邻接列表。此外，还定义了一个名为 isCyclic 的方法，该方法执行图的 BFS 遍历来查找环。在将零入度的顶点入队之前，isCyclic 函数会确定每个顶点的入度。然后，它会移除零入度的顶点并降低其相邻顶点的入度。任何入度为零的相邻顶点都会被入队。如果不是所有顶点都已访问，表明存在环，则该方法返回 true 并跟踪已访问顶点的数量。

代码

输出

The graph has a cycle

时间复杂度: 我们遍历了总的顶点数和边数。因此，时间复杂度为 O(V + E)。

空间复杂度: 我们创建了一个数组来存储已访问的节点。因此，空间复杂度为 O(V)。