C++ 中 Tarjan 算法查找强连通分量

Tarjan 算法，作为大多数相关图算法的基础，用于发现有向图中的强连通分量（SCS）。SCC 是图的基本构建块。因此，组件中的每个顶点都可以访问组件中的任何其他顶点。事实上，这些路径是循环的，因此总有一条路径从任何顶点开始，到达另一个顶点，然后返回到已访问过的顶点。

DFS（深度优先搜索）方法非常有效，因为它在图上提供了出色的性能。通过 DFS 的搜索算法将花费时间深入探索顶点。在宽松的策略方案中，顶点被分配顺序不同的编号。由于缺少“地址”，无法遍历整个图结构，但堆栈允许 DFS 克服此问题。

正是这种方法可以实现资源的最佳利用，并且还有助于图的遍历、路径查找和网络分析。因此，这种过程是必不可少的，可以用于任何需要高效地对图数据结构进行调查的应用程序。

这可以通过不断更新每个顶点的发现时间，并找到通过图的有向边和反向边可以到达的最低顶点来实现；这使得Tarjan 方法能够将强连通分量（SCC）与图的其余部分分开。该算法在遇到其发现时间匹配的顶点时，会比较一个顶点的最低祖先；这是为了找到另一个新的，然后通过从堆栈中提取各种顶点直到到达当前顶点来继续。

方法 1：使用邻接表表示法

在数据结构中存储图最流行的方式是邻接表表示法。边列表在 C++ 代码中表示为数组或向量，其中每个元素对应于图中的一个顶点。数组的每个元素（边）是一个列表，其元素（节点）表示与其对应的顶点的相邻顶点。它包含此邻接列表以揭示顶点之间的连通性。因此，它便于遍历和操作，这非常重要。

边列表表示法在 Tarjan 算法等针对图中的 SCC 的算法中特别有利。通过这种表示法，可以轻松地进行顶点的邻域以及图操作，这意味着依赖于图连接和结构的算法可以高效运行。归根结底，正是邻接表表示法的强大功能使其在 C++ 编程中存储和操作图方面具有通用性和高效性。

程序

输出

Strongly Connected Components:
4 
3 
2 1 0

说明

• Graph 类
  Graph 类使用邻接表表示法实现了有向图。它具有用于跟踪顶点数量和邻接列表（adj）的成员变量，邻接列表（adj）是一个向量的向量。每个内部向量是顶点的邻接列表。构造函数初始化顶点数量并调整邻接列表的大小以适应此数量。
• 添加边
  addEdge 函数用于此方式，以建立图节点之间的链接。它接受两个参数：e，它连接顶点 v 到顶点 w，是边。将新入边 w 添加到 v 的邻接列表中，表示从 v 到 w 的有向链接。
• 深度优先搜索 (DFS)
  深度优先搜索 (DFS) 算法从起始顶点 u 开始线性遍历图，在边标记过程中维护发现时间 (disc) 和最低祖先 (low)。它利用堆栈 (st) 来跟踪探索动量，并使用 stackMember 向量来识别当前在堆栈中的顶点。DFS 在回溯之前尽可能深入地探索每个分支，从而以深度优先的方式有效地遍历图。通过系统地访问顶点并标记其发现时间和最低祖先时间，DFS 有助于执行诸如循环检测、拓扑排序以及在图中查找强连通分量等任务。
• 查找强连通分量
  当 findSCCs 方法进入时，它会初始化 disc 和 low 数组来计算顶点的发现时间、最低祖先和 stackMember 状态。它扫描图中的所有顶点，并将它们放入一个名为 disc[] 的 n 维数组中，其当前索引未被访问 (disc[i] == -1)。
  在 DFS 过程中，我们应该寻找最低祖先值等于其自身发现时间 (low[u] == disc[u]) 的节点 u，这将指示强连通分量的开始。然后将队列中的顶点对馈入堆栈，当堆栈变空时，达到顶点 u，从而形成一个强连通分量。之后，它与所有 SCC 的向量合并。
• 主函数
  main 函数通过创建一个空的有向 Graph 对象并添加顶点(V)和边与 Graph 类开始。图中的边通过 addEdge 方法获得，在该方法中算法添加了这些连接不同顶点之间的连接。然后，使用 strongly connected components (SCCs) findSCCs 方法来检查强连通分量的存在。这些 SCC，作为实体单元，包含所有顶点子集，这些子集覆盖了每个顶点与每个其他顶点。

结构化社群已被识别并打印出来，以便能够通过整个图来讲述网络连接的故事。这实际上促进了对图进行强分析和理解的过程，从而也促进了组成元素之间的关系。

复杂度分析

时间复杂度

该算法的时间复杂度为O(V+E)，其中 V 是顶点数，E 是图中的边数。DFS 遍历是该算法的关键组成部分，每个顶点和边最多访问一次，因此时间复杂度为 O(V+E)。此外， whilst 查找强连通分量是通过一次遍历图的顶点和边来完成的，它需要额外的O(V + E)，这会加剧整体时间复杂度。

与边和顶点直接相关意味着该算法在分析大型图方面效率很高，因此适合用于此目的。通过优化利用图的拓扑结构及其派生物，Tarjan 算法成功地识别了对深入图分析至关重要的强连通分量。

空间复杂度

该算法的空间复杂度主要由用于表示图和保存 DFS 遍历所需临时项的数据结构定义。

邻接表表示的空间复杂度为O(V + E)，其中 V 是顶点数，E 是有向弧数，因为对于无向图，每条边都单独计数。这就是每个顶点都有一个相邻顶点列表的原因。

另一方面，在发生DFS 遍历时，会存储全局向量以检索发现时间、最低祖先值、堆栈成员状态以及堆栈成员。这些工具总共形成一个O(V)复杂度的数据结构。

因此，该算法的空间复杂度顺序为 O(V + E)，由邻接表表示法表示图的空间复杂度所主导。

方法 2：使用哈希表

Tarjan 算法，它执行统一查找有向图的所有强连通分量（SCC）的任务，是一种通用的解决方案，适用于各种数据结构，如哈希表、哈希集。它们通过帮助算法快速移动和管理关于顶点和边的拓扑信息来提高算法的速度，从而能够更快地识别 SCC。

通过巧妙地部署这些数据结构来最优地遍历图，并通过实现此算法；它能够以几乎零计算成本有效地识别和聚类图的强连通分量。这种能力表明该算法如何服务于各种图表示以及不同大小的图，同时仍能以预期的最高标准运行。

程序

输出

Strongly Connected Components:
8 
9 
1 5 7

说明

Graph 类

使用图类的方向属性和元素的邻接列表来符号化。构造函数初始化 V（顶点），而方法允许识别强连通分量。通过addEdge，建立节点之间的边，从而增强图的连通性。

发生的事件与findSCCs 相反，后者依赖于 Tarjan 算法来暴露与内聚顶点子集相关的连通分量。这种抽象代表了图中的不同顶点，因此可以精确地操作顶点集，从而可以将其应用于广泛的图论相关算法。

DFS 函数

DFS 函数执行深度优先搜索，遍历图的节点以查找超级分量。

图查找算法从起始顶点 u 开始，并跟踪访问的顶点数量和当前的DFS 遍历路径，使用堆栈 (st) 来维护DFS 遍历顺序，使用向量的向量 (SCCs) 来存储已识别的强连通分量，以及用于映射到每个顶点的最低祖先(low) 和查找从一个顶点到另一个顶点的过渡时间的数据结构。

在进行深度优先搜索遍历时，它会确定每个顶点的发现时间和最低祖先，并通过将其存储在堆栈和集合中来记录属于当前 DFS 路径的顶点。它通过验证其最低祖先是否与发现时间相同来确定过程的 SCC。如果是，则从堆栈中弹出顶点，从而形成一个 SCC。

FindSCCs 函数

在 Graph 类中，findSCCs 函数充当指挥家，通过深度优先搜索（DFS）遍历快速找到强连通分量（SCC）。它从每个顶点开始，开发诸如发现时间、最低祖先、堆栈以及包含当前遍历路径中顶点的存储库之类的数据结构。通过遍历所有顶点，它为任何未访问的节点调用DFS 函数来查找图的邻接关系。

在执行过程中遍历图时，算法负责更新发现时间和识别最低祖先，这两者对于识别 SCC 都至关重要。当检测到 SCC 时，这些 SCC 会被收集并存储在向量中以供将来审查。整个DFS 过程用于扫描整个图并深入探索，并且在调用 SCC 函数执行后，可以找到图的结构组织和连接的重要信息。

主函数

Main 函数与描述图边的 Graph 对象一起创建。首先，使用 addVertex 方法创建每个节点并将其添加到图中。然后使用addEdge 方法将边添加到图中，该方法将节点彼此连接。接下来，将调用 findSCCs 方法，它将检测图中的强连通分量。作为此功能的一部分，Tarjan 算法用于遍历图。

通过这样做，可以识别顶点簇，这些簇又会根据它们与其他顶点的连接方式形成 SCC。最后，将考虑的 SCC 存储在控制台中，控制台将显示图的结构组织。因此，此过程使我们能够可视化和研究具有相似特征属性的图的片段，以进行顶点分布；网络分析、交通导航和群组分类。

复杂度分析

时间复杂度

主要时间复杂度是由于对图进行的深度优先搜索（DFS）遍历。考虑到算法只遍历每个部分和链接一次，时间复杂度基本上由V 和 E描述，它们分别表示图中的顶点数和边数。

在最坏的情况下，图是密集连接的，任何一个节点都可以到达任何其他节点，这导致 DFS 遍历的时间复杂度为O(V + E)。这是因为在遍历过程中，每个顶点和边只被访问一次。

此外，在DFS 遍历中查找 SCC 的过程包括诸如分配发现时间和最低祖先值之类的操作，以及检查启用SCC 识别的条件。除了计算机操作之外，DFS 遍历也涉及大部分的复杂性。

总之，该算法的总复杂度为O(V + E)，其中 V 是顶点数，E 是整个图中的边数。

空间复杂度

该算法的空间复杂度主要涉及在 DFS 遍历期间存储信息以及查找图中强连通分量所需的任何额外数据结构。

以邻接列表格式表示图的空间利用率为O(V + E)，其中 V 是顶点数，E 是边数。

DFS 遍历需要一些额外的空间用于记录发现时间、最低祖先的映射，以及用于保存历史记录的堆栈，以及用于当前路径中顶点的使用集。这些数据结构的空间复杂度为O(V)。

存储已识别 SCC 图形的空间复杂度由 SCC 的数量和每个 SCC 中顶点的数量决定。在汇点情况（其中每个顶点都是汇点且顶点本身）下，最坏空间为 V。然而，实际上，SCC 的数量远小于顶点数量，因为图是共享的。

因此，该算法的最终空间复杂度为O(V + E)，这由存储图表示所需空间和DFS 遍历期间使用的数据结构所主导。