在 C++ 中检测无向图中的循环

引言

图是一种基本的数据结构，用于模拟实体之间的关系。在图中检测环是计算机科学中的一个常见问题，并且对于网络路由和资源分配等各种应用至关重要。

无向图

无向图由一组顶点和一组边组成，其中每条边连接两个顶点。在无向图中，边没有方向，这意味着两个顶点之间的连接是双向的。检测此类图中的环涉及识别一个顶点序列，其中第一个和最后一个顶点相同。

算法 - 深度优先搜索 (DFS)

在无向图中检测环的常用算法之一是深度优先搜索 (DFS)。基本思想是对图进行深度优先遍历，标记每个已访问的顶点。

算法步骤

1. 从任意节点开始 DFS。
2. 将当前节点标记为已访问。
3. 对于当前节点的每个邻居
   • 如果邻居未被访问，则递归地重复步骤 a-c。
   • 如果邻居已被访问且不是当前节点的父节点，则检测到环。

基于 DFS 的环检测基于这样一个事实：如果在 DFS 过程中遇到一个已访问的节点，并且它不是当前节点的父节点，那么就存在一条反向边，表明存在环。

图解

考虑以下无向图

让我们逐步浏览 DFS 算法在此图上检测环的过程

• 从节点 A 开始。
• 将 A 标记为已访问。
• 遍历 B 和 C。
• 移动到 B，将其标记为已访问。
• 遍历 D 和 E。
• 移动到 D，将其标记为已访问。
• 遍历 B（已访问，但不是父节点），检测到环 (B - D)。
• 回溯到 A。
• 遍历 C（已访问，但不是父节点）。
• 移动到 E，将其标记为已访问。
• 遍历 D（已访问，但不是父节点），检测到环 (D - E)。
• 回溯到 C。
• 回溯到 A。

实施

说明

• 该程序定义了一个名为 Graph 的类来表示无向图。它具有私有 **成员变量**，**vertices**（图中的顶点数）和 **adjList**（用于存储边的邻接列表）。
• 该类包含一个构造函数，用于初始化具有给定数量 **vertices** 的图，一个 **addEdge** 方法用于在顶点之间添加边，以及一个 **isCyclic** 方法用于检查图是否包含环。
• **addEdge** 方法用于在图中的两个顶点之间添加边。它接受两个参数 **u** 和 **v**，代表要连接的顶点。由于图是无向的，因此该方法将 v 添加到 u 的邻接列表中，反之亦然。
• **isCyclicUtil** 方法是环检测算法的辅助函数。它使用深度优先搜索 (DFS) 来遍历图并检测环。
• 它接受三个参数：当前顶点 v，一个布尔值向量 visited 用于跟踪已访问的顶点，以及当前顶点的父节点。如果检测到环，则函数返回 true，否则返回 false。
• **isCyclic** 方法是检查图是否包含环的主要函数。它初始化一个 visited 向量来跟踪已访问的顶点，并使用循环遍历所有顶点。
• 如果一个顶点未被访问，它会为该顶点调用 **isCyclicUtil** 函数。如果 **isCyclicUtil** 返回 true，表示存在环，则 **isCyclic** 方法返回 true；否则，它继续到下一个未访问的顶点。如果遍历完所有顶点后未找到环，则该方法返回 false。
• main 函数创建了一个具有 5 个顶点的 Graph 类实例。然后添加边以创建示例图。最后，它调用 **isCyclic** 方法并根据返回值打印图是否包含环。

程序输出

并查集

并查集，也称为不相交集合∪（DSU），是另一种强大的环检测技术。它对于具有大量节点的图特别有用。

算法步骤

为每个节点创建一个不相交集。

对于每条边 (u, v)

• 查找包含 u 的集合的代表（根）。
• 查找包含 v 的集合的代表。
• 如果代表相同，则检测到环。
• 否则，将包含 u 和 v 的集合进行并集操作。

并查集通过维护不相交集合并有效地确定添加边是否会创建环来工作。并集操作确保通过边连接的节点属于同一集合，从而防止形成环。

说明

• 该程序定义了一个 **UnionFind** 类，它是一种用于有效管理不相交集合的数据结构。
• 它包含一个 parent 数组，其中每个元素代表一个集合的父节点。构造函数使用 -1 初始化 parent 数组，表示每个元素最初是自己的父节点。
• find 方法递归地查找集合的根（代表），而 **unionSets** 方法通过将一个集合的父节点指向另一个集合的根来合并两个集合。
• 该程序还定义了一个 Graph 类，它表示一个无向图。它有一个成员变量 vertices 用于存储顶点数，以及一个 vector edges 用于将边存储为顶点对。
• 构造函数初始化顶点数， **addEdge** 方法允许向图中添加边。
• Graph 类有一个名为 **isCyclic** 的方法，该方法使用并查集算法来确定图是否包含环。它遍历图的边，对于每条边，它查找边顶点所属集合的根。
• 如果根相同，则表示顶点属于同一集合，添加边将形成环。如果根不同，则使用 **unionSets** 合并集合。如果检测到任何环，则该方法返回 true，否则返回 false。
• 在 main 函数中，创建了一个具有 5 个顶点的 Graph 类实例。然后添加边以形成示例图。
• 然后调用 **isCyclic** 方法来检查图是否包含环。最后，根据结果，程序输出图是否包含环。

程序输出

结论

总之，在无向图中检测环是计算机科学和图论中的一个关键问题，在网络分析、路由算法和资源分配等各个领域都有应用。在 C++ 中实现环检测算法对于程序员和软件工程师来说是一项宝贵的技能，使他们能够构建能够处理循环依赖并防止意外后果的健壮系统。

在算法解决方案领域，无向图中检测环通常涉及使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 等技术来遍历图。这些算法在有效识别环方面起着基本作用，并且可以通过对图论原理的清晰理解在 C++ 中实现。通过成功检测环，开发人员可以提高其应用程序的可靠性和稳定性，防止出现无限循环或意外的循环依赖等问题。

此外，环检测算法的实现展示了算法思维和解决问题技能在软件开发中的重要性。它举例说明了程序员如何将理论概念应用于实际场景，强调了对数据结构和算法有扎实基础的需求。