C 语言 Kosaraju 算法

Kosaraju 算法在 C 语言中的实现是图论和算法中最基本概念之一。在有向图中，强连通分量 (SCC) 是一个顶点集，其中每个顶点都可以从该集合中的其他每个顶点通过有向边到达。查找图中所有 SCC 的问题是一个有趣的案例研究，这个问题可以通过多种方式得到解决。这些数据可以提供有关图的结构和连通性的见解，并在社交网络、社交网络分析、网络爬行和网络路由等领域有许多应用。

什么是 Kosaraju 算法？

如果可以从强连通分量内的任何顶点遍历到任何其他顶点，则称一个有向图是强连通的。单个有向图可以有多个强连通分量。图中的连通性是指两个顶点是否可以相互到达。如果从路径的角度定义连通性，那么如果一条路径存在从一个顶点到另一个顶点，则这两个顶点被认为是连通的。

Kosaraju 算法是一种基于深度优先搜索 (DFS) 的算法，用于查找有向图的所有强连通分量 (SCC)。该算法的魅力在于它能将所有可达顶点紧凑地合并到单个 SCC 中。换句话说，该算法查找图的所有 SCC，并返回一个包含所有可达顶点的子图。

该算法分两个主要阶段进行。

• 在原始图上运行 DFS，并将顶点压入堆栈，因为它们已完成或在回溯时标记为已访问。在此步骤中，我们不查找原始图的 SCC；我们只查找完成时间。
• 反转图中的所有边的方向，然后使用与之前相同的 DFS 过程再次运行：首先，重置我们在第一步中保存的所有顶点的完成时间。在此步骤之后，每次调用此 DFS 都将返回一个 SCC。

下面概述了实现 Kosaraju 算法以查找有向图的所有强连通分量的步骤

步骤：

• 对正在考虑的有向图执行深度优先搜索 (DFS) 遍历，并使用空堆栈（或任何允许 DFS 的数据结构）。搜索操作在顶点上执行。
• 之后，反转图中的每条边的方向，得到一个具有相同顶点但方向相反的新图。可以通过切换每条边的源顶点到目标顶点来完成此方向反转。
• 接下来，从堆栈中逐个弹出顶点，然后对从堆栈中弹出的每个顶点在反向图上执行 DFS。在对从堆栈中弹出的每个顶点执行 DFS 后，在单次遍历/DFS 中一起到达的顶点集将与所选顶点的强连通分量相关。
• 重复步骤 3，直到堆栈为空。每次为堆栈中的顶点执行 DFS 时，都会有一个与从堆栈中弹出的顶点相关联的新强连通分量。
• Kosaraju 的方法在步骤 3 的反向图上进行 DFS 遍历，返回额外的新的强连通分量。这些分量代表有向图中的强连通顶点组，并且每个强连通分量都通过顶点间的连通性来表征。

实现 Kosaraju 算法的用途是什么？

Kosaraju 算法应用于有向图以查找强连通分量。强连通分量是顶点集，其中存在从强连通分量中的每个顶点到该强连通分量中的每个其他顶点的至少一条有向路径。

在有向图中应用 Kosaraju 算法的考虑因素包括

• 时间复杂度效率： Kosaraju 算法的时间复杂度为 O(V + E)，其中 V 和 E 分别代表有向图中的顶点数和边数。你强调 O(V + E) 是线性时间复杂度，这使得 Kosaraju 算法在不仅仅是大型图，而且在任何实际持久实现都将是大型图的现实建模情况中特别有吸引力。
• 简洁性和可实现性迭代： 与 Tarjan 或 Gabow 等其他强连通分量搜索算法相比，Kosaraju 算法的指令非常明确且简单。Kosaraju 算法简单地恰当地描述为两阶段深度优先搜索 (DFS) 过程，即一个 DFS 过程后跟另一个 DFS 过程，但是在反向有向图上。
• 查找强连通分量： 尽管使用 Kosaraju 算法有一些不同的考虑因素，但你注意到强连通分量在数据库管理、网络分析、社交网络或构建编译器中有广泛的应用。查找强连通分量可以显示有向图中包含的信息的结构和行为，但查找强连通分量也可以提供在实际问题解决中的价值。
• 稳健性： Kosaraju 算法查找并识别有向图中的所有强连通分量，而不管有向图是完全断开连接的还是部分断开连接的。无论有向图是否完全分区，或者顶点是否无法完全或部分地相互到达，Kosaraju 算法都会查找强连通分量。
• 灵活性： 该算法可以针对其他有向图分析和研究目的进行改编。例如，Kosaraju 算法可以改编用于有向图中基于顶点数量的 k 个最大的强连通分量，或者基于其他条件指标查找强连通分量。

Kosaraju 算法的工作原理

在有向网络中，Kosaraju 算法以线性时间识别强连通分量 (SCC)。它可以称为前向阶段和反向阶段。以下是该算法工作原理的总体概述

1. 前向阶段

从图中的任意顶点开始，并对其进行深度优先搜索 (DFS)。通过执行此 DFS，每个顶点都将被赋予一个“完成时间”，即每个顶点在 DFS 遍历期间完成的时间。

根据完成时间顺序记录顶点，最可能的是使用一个堆栈来存储完成的顶点。

2. 反向阶段

反转每个边的方向以进行转置，然后从堆栈中弹出顶点。在转置图上执行 DFS 搜索。在此步骤中，原始图已识别出源自从被弹出顶点执行的 DFS 的强连通分量。

示例

输出

 
The Strongly Connected components of the graph are:
0 2 1
3
4   

说明

方法

下面的函数用于查找最强的连通分量。

图结构

定义了 Graph 结构，其中包含

• Int vertex： 表示图中的顶点数。
• Int adjM[MAX][MAX]： 一个邻接矩阵，用于表示顶点之间的边，MAX 的值是预定义的，表示顶点的最大数量

Stack Structure： Stack 结构用于在 DFS 遍历期间存储顶点的顺序。

• Int item[MAX]： 将用于存储所有堆栈项的数组。
• Int peek： 一个整数用于指示堆栈的顶部。最初，设置为 -1 表示堆栈为空。

函数

• 代码使用几个函数来执行所需的算法
• 创建堆栈： 函数 (creationOfStack) 将用于创建一个新的堆栈，它会为堆栈分配内存并将 peek 索引初始化为 -1。
• 压入和弹出项： 压入和弹出过程处理要压入和弹出的元素。push 函数将用于通过增加 peek 索引将顶点压入堆栈，而 pop 函数将用于从堆栈中弹出顶点并减少 peek 索引。
• 检查堆栈是否为空： StackisEmpty 将用于检查堆栈是否为空。

DFS

必须实现 dfs 函数来对原始图执行深度优先搜索。将当前顶点标记为已访问。

• 图的转置： getGraphTranspose 函数将对图进行转置。
• 在转置图上进行 DFS： 与第一次 DFS 类似，我们将在转置图上实现 DFS 函数。

Kosaraju 算法

核心函数 kosarajuAlgo 运行该算法

• 第一次 DFS 调用： 它遍历所有顶点并调用 dfs 函数，根据完成时间填充堆栈。
• 转置图： 调用 getGraphTransposeto 创建一个转置图。
• 重置 visited 数组： 我们重置 visited 数组以准确跟踪第二次 DFS。
• 第二次 DFS 调用： 它从堆栈中弹出顶点，并对发现的未访问顶点调用 dfsTransposeGraph。这使我们能够查找和打印 SCC。

主函数

设置顶点数。将邻接矩阵初始化为零。之后，根据指定添加有向边。最后，它调用 kosarajuAlgo 来运行算法并打印找到的强连通分量。

结论

总之，Kosaraju 算法代表了一种高效有效的方法来查找有向图中的强连通分量 (SCC)。该方法在 O(V + E) 时间内运行，对于大型图尤其有用，能够触及其在社交网络分析、网络爬行和网络路由等许多应用中的实际用途。

Kosaraju 简洁灵活的算法包含对有向图的两次深度优先搜索 (DFS)。通过反转图并利用堆栈确定顶点处理顺序，该算法可以准确地识别 SCC，而无论有向图是否已连接。