Python中检测无向图中的循环

在此问题中，我们将被给定一个无向图。我们在该问题中的任务是判断给定图是否存在环。

让我们通过一些图示来理解图中的环是什么样的。

示例

输入: N = 8, E = 8

输出： 是

解释: 图表显示存在一个环。

方法 - 1

在第一种方法中，我们将使用深度优先搜索 (DFS) 算法来查找图中的环。

计划是对邻接表的所有未访问节点使用 DFS 算法。我们必须多次使用该算法，以确保连通分量也被遍历并检查它们是否包含环。我们将创建一个数组来记录当前节点是否已被访问。此外，我们还需要记录当前节点的父节点。对于当前节点的每个邻居，我们仅当该节点未被访问时才递归调用函数来检测环。但是，如果该节点已被访问，我们将检查该节点是否是当前节点的父节点；如果是，则它不能构成环。但如果当前节点不是父节点，并且仍然已被访问，则意味着图中存在环。让我们通过一个例子来理解这个概念。

考虑一个图

• 现在，当我们从 1 开始时，我们将检查邻居并为邻居节点 2 调用函数。同样，2 的父节点是 1。现在执行函数 2，我们将遍历 2 的邻居节点。其中一个邻居节点是 1。1 已经被访问；然而，1 也是父节点，所以它不代表环。
• 对于节点 8，当遍历 4 的邻居节点时，它将已经被访问。
• 当我们到达 7 时，其父节点是 6，并且我们检查 7 的邻居元素，8 已经被访问。7 的父节点不等于 8；因此，它表示一个环。因此，程序将返回 True。
• 我们必须为图的每个连通分量返回此算法。
• 我们将按照以下步骤使用 DFS 来解决此问题。
  • 我们将创建一个函数 Cyclic()，它将接受图的邻接表和图中存在的顶点数。我们将创建一个长度等于顶点数的数组 vis[]。此数组将初始化为零数组，因为开始时没有任何节点被访问。
  • 在此函数中，我们将运行一个 for 循环来为图的所有分量运行检测函数。
  • 我们将创建另一个函数 detect()，它将接受邻接表、起始顶点、vis[] 和给定顶点的父节点。
    • 在函数内部，第一步是标记 vis[vertex] = 1。
    • 然后，我们将遍历给定顶点的邻居节点。
    • 我们将检查当前邻居节点是否未被访问，然后我们将递归调用 detect 函数来处理此节点。如果此函数对某个调用返回 True，则意味着存在环；因此，我们将返回 True。
    • 如果当前邻居节点已被访问，我们将检查该节点是否与当前顶点的父节点不同。如果访问过的节点与父节点不同，则意味着图中存在环。因此，我们将返回 True。
    • 如果循环在未返回 True 的情况下完成，则我们将返回 False，这意味着当前连通分量的图中没有环。
  • 在 Cyclic() 函数中，detect() 函数将被调用来处理图的每个分量。如果没有任何分量包含环，它将返回 False。

代码

输出

The graph contains a cycle
The graph doesn't contain a cycle

时间复杂度: 由于我们维护了已访问节点数组，因此我们不会对某个节点调用 detect() 函数两次以上。因此，我们只访问每个节点和边一次。因此，DFS 算法的时间复杂度是线性的。总时间复杂度等于顶点数和边数之和，即 O(V+E)，其中 V 是顶点数，E 是边数。

辅助空间: 我们使用空间来存储已访问数组。因此，空间复杂度为 O(V)。用于存储递归栈的空间。

方法 - 2

在这种方法中，我们将使用 BFS 算法来检测给定图中的环。

在广度优先搜索算法中，我们按层级访问节点。首先，我们完成访问特定级别的节点，然后移至下一个级别。BFS 算法是使用队列数据结构实现的。队列在 BFS 中使用，因为队列遵循先进先出 (FIFO) 的方法。因此，我们访问同一级别的所有节点，因为它们会比下一级别的节点先添加到队列中。

这里的 BFS 将被修改。正如我们在前一种方法中所见，检测环的基本思想是检查节点是否已被访问，如果已被访问，则它不应该是当前源节点的父节点。因此，我们需要跟踪当前源节点的父节点。因此，在队列中，我们不仅添加节点，还添加一个包含节点及其相应父节点的列表，以便在每次迭代中检查已访问节点是否与父节点不同。

我们将按照以下步骤解决此问题。

• 这里我们需要创建两个数据结构；第一个是用于执行 BFS 遍历的队列。第二个是用于标记节点是否已被访问的数组。
• 我们将初始化长度等于顶点数的已访问数组，并将其值设置为 0，表示没有节点被访问。
• 我们将从第一个节点开始，即索引为 0 的节点。
• 我们将标记 vis[0] = 1。我们也需要将此节点添加到队列中。在队列中，我们将添加一个结构为 [<节点>, <对应的父节点>] 的列表。第一个节点没有父节点，因此我们将添加 -1。所以，队列将被初始化为 [[0, -1]]。
• 现在，我们将使用 while 循环开始 BFS 遍历。
  • 在每次迭代中，我们将从队列中弹出第 0 个节点，并存储节点及其父节点。
  • 然后，我们将使用 for 循环遍历此节点的邻接表。
    • 在 for 循环中，我们将检查当前邻居节点是否已被访问。
    • 如果此节点未被访问，那么我们将标记它已被访问，并将此节点添加到队列中。现在，我们还需要添加父节点；因此，我们将添加 [i, n]，其中 n 是当前迭代中从 q 中弹出的节点。
    • 然而，如果节点已被访问，那么我们将检查这个 ith 节点是否与节点 n 的父节点不同。
    • 如果是，则意味着存在环，我们将返回 True。
  • 如果 while 循环在未中断的情况下结束，则我们将返回 False，即不存在环。
  • 我们需要为给定图的每个分量重复此过程。因此，我们将为图的每个未访问节点调用 bfs() 函数。

以下是此方法的 Python 程序。

代码

输出

The graph contains a cycle
The graph doesn't have a cycle

时间复杂度: 我们使用线性循环来遍历图。由于我们只访问邻接表的每个节点一次，因此迭代次数等于顶点数和边数之和。因此，时间复杂度为 O(V+E)。

空间复杂度: 我们使用 O(V) 内存来存储已访问数组。