Tarjan 算法与 Kosaraju 算法的比较
Tarjan 算法用于定位有向图中的强链接组件，Robert Tarjan 于 1972 年创建了称为 Tarjan 算法的图遍历技术。它无需遍历先前处理的节点，而是使用深度优先搜索策略和堆栈数据结构有效地定位和处理每个高度相关的组件。该算法经常用于计算机科学和图论，有多种用途，包括算法创建、网络分析和数据挖掘。
Kosaraju 算法包括两次遍历图。在第一次遍历中，以相反的顺序遍历图，并为每个节点分配"完成时间"。在第二次遍历中，按完成时间的顺序访问节点，并识别和标记每个强链接组件。
Tarjan 算法方法
在本例中，Graph 类在程序开始时定义，其构造函数根据图中的顶点数初始化邻接列表数组。通过将目标顶点包含在源顶点的邻接列表中，addEdge 函数向图中添加一条边。
SCCUtil 方法是一种基于 DFS 的递归函数，SCC 方法利用该方法发现 SCC，该方法构成了该程序的基础。当前顶点 u、发现时间 disc 数组、低值 low 数组、顶点堆栈 st 数组以及跟踪顶点是否在堆栈中的布尔值 stackMember 数组是此函数的输入。
该过程将当前顶点放入堆栈，并在首先为其分配发现时间和低值后将其 stackMember 值更改为 true。之后，它以递归方式将所有附近顶点的低值更新为当前顶点。
该技术迭代访问未发现的顶点 vs 并修改 u 的低值。如果 v 已在堆栈中，则该方法根据 v 的发现时间修改 u 的低值。
算法 Tarjan
初始化算法
开始遍历图
检查强连通分量
重复，直到所有节点都已被访问
返回强连通分量
该方法将所有顶点从堆栈中弹出，直到当前顶点 u 被弹出，打印弹出的顶点，并且如果 u 是头节点(即，如果其低值等于其发现时间)，则将其 stackMember 值设置为 false。
示例
// 使用 Tarjan 算法(单 DFS)查找 SCC 的 C++ 程序
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
// 表示有向图的类
class Graph {
// 顶点数
int V;
// 邻接列表的动态数组
list<int>* adj;
// 基于递归 DFS 的函数
// 由 SCC() 使用
void SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]);
public:
// 成员函数
Graph(int V);
void addEdge(int v, int w);
void SCC();
};
// 构造函数
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// 向图添加边的函数
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
// 递归函数查找 SCC
// 使用 DFS 遍历
void Graph::SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]) {
static int time = 0;
// 初始化发现时间
// 和低值
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;
// 遍历所有顶点
// 与此相邻
list<int>::iterator i;
for (i = adj[u].begin();
i != adj[u].end(); ++i) {
// v 是 'u' 的当前相邻元素
int v = *i;
// 如果 v 尚未被访问，
// 则对其重复访问
if (disc[v] == -1) {
SCCUtil(v, disc, low, st, stackMember);
// 检查以 'v' 为根的子树是否与
// 'u' 的祖先之一有连接
low[u] = min(low[u], low[v]);
}
// 仅更新 'u' 的低值
// 'v' 仍在堆栈中
else if (stackMember[v] == true)
low[u] = min(low[u], disc[v]);
}
// 找到头节点，弹出堆栈
// 并打印 SCC
// 存储堆栈提取的顶点
int w = 0;
// 如果 low[u] 和 disc[u]
if (low[u] == disc[u]) {
// 直到堆栈 st 为空
while (st->top() != u) {
w = (int)st->top();
// 打印节点
cout << w << " ";
stackMember[w] = false;
st->pop();
}
w = (int)st->top();
cout << w << "\n";
stackMember[w] = false;
st->pop();
}
}
// 在图中查找 SCC 的函数
void Graph::SCC() {
// 存储节点的发现时间
// int* disc = new int[V];
// 存储发现时间最少的节点
// int* low = new int[V];
// 检查节点是否在堆栈中
// bool* stackMember = new bool[V];
// 存储所有连接的祖先
stack<int>* st = new stack<int>();
// 初始化 disc 和 low，
// 和 stackMember 数组
for (int i = 0; i < V; i++) {
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}
// 递归辅助函数，用于
// 在 DFS 树中找到具有
// 顶点"i"的 SCC
for (int i = 0; i < V; i++) {
// 如果当前节点尚未被访问
if (disc[i] == NIL) {
SCCUtil(i, disc, low, st, stackMember);
}
}
}
// 驱动代码
int main() {
// Given a graph
Graph g1(5);
g1.addEdge(3, 5);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(4, 3);
g1.addEdge(3, 4);
// 函数调用使用 Tarjan 算法查找 SCC
g1.SCC();
return 0;
}
输出
1 2 0 4 3
方法 2- Kosaraju
Kosaraju 算法
启动时创建一个访问过的节点集合和一个空堆栈。
从图中每个节点中第一个未被访问过的节点开始深度优先搜索。将搜索过程中访问过的每个节点推送到堆栈上。
每个图边的方向都应该反转。
如果堆栈中仍充满节点，则从堆栈中弹出节点。 如果尚未访问节点，则从该节点执行深度优先搜索。将搜索过程中访问过的每个节点标记为当前高度链接组件的成员。
直到所有节点都被访问过，重复
。
每个高度链接的组件都将被识别并在程序结束时记录下来。
下面的 C++ 代码使用 Kosaraju 算法在有向图中查找强连通组件 (SCC)。该软件定义了一个名为 Graph 的类，它具有以下成员函数:
Graph(int V):构造函数，输入顶点数 V 并初始化图的邻接列表。
Void addEdge(int v, int w):使用两个整数 v 和 w 作为输入，此方法在图中创建一条连接顶点 v 和顶点 w 的边。
void printSCCs() 函数使用 Kosaraju 算法打印图中的每个 SCC。
Graph getTranspose() 方法提供图的转置。
使用递归函数 void fillOrder(int v, bool accessed[, stack& Stack], int v)，按完成时间的顺序将顶点添加到堆栈中。
示例 2
// C++ 程序使用 Kosaraju 算法打印
// 图的 SCC
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
// 顶点数
int V;
// 邻接列表数组
list<int>* adj;
// 成员函数
void fillOrder(int v, bool visited[],
stack<int>& Stack);
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void printSCCs();
Graph getTranspose();
};
// 类的构造函数
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// 递归函数打印 DFS
// 从 v 开始
void Graph::DFSUtil(int v, bool visited[]) {
// 将当前节点标记为
// 已访问并打印
visits[v] = true;
cout << v <<" ";
// 对所有顶点进行递归
// 与此顶点相邻
list<int>::iterator i;
// 遍历节点 v 的邻接列表
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// 如果子节点 *i 未被访问
if (!visited[*i])
DFSUtil(*i, visited);
}
}
// 获取给定图的转置的函数
Graph Graph::getTranspose() {
Graph g(V);
for (int v = 0; v < V; v++) {
// 对所有顶点进行递归
// 与此顶点相邻
list<int>::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// 添加到邻接表
g.adj[*i].push_back(v);
}
}
// 返回反转图
return g;
}
// 函数用于将边添加到给定的
// Graph
void Graph::addEdge(int v, int w) {
// 将 w 添加到 v 的列表中
adj[v].push_back(w);
}
// 函数用于按完成时间的递增顺序用顶点填充堆栈
//
void Graph::fillOrder(int v, bool visited[],
stack<int>& Stack) {
// 将当前节点标记为
// 已访问并打印
visited[v] = true;
// 对所有与此顶点相邻的顶点
list<int>::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// 如果子节点 *i 未被访问
if (!visited[*i]) {
fillOrder(*i, visited, Stack);
}
}
// 从 v 可到达的所有顶点
// 现在都已处理，推送 v
Stack.push(v);
}
// 查找并打印所有
// 强连通分量的函数
void Graph::printSCCs() {
stack<int> Stack;
// 将所有顶点标记为
// 未访问(对于第一个 DFS)
bool* visit = new bool[V];
for (int i = 0; i < V; i++)
visit[i] = false;
// 根据完成时间在堆栈中填充顶点
for (int i = 0; i < V; i++)
if (visited[i] == false)
fillOrder(i, visited, Stack);
// 创建反转图
Graph gr = getTranspose();
// 将所有顶点标记为
// 未访问(对于第二个 DFS)
for (int i = 0; i < V; i++)
visit[i] = false;
// 现在按照 Stack 定义的顺序处理所有顶点
while (Stack.empty() == false) {
// 从堆栈中弹出一个顶点
int v = Stack.top();
Stack.pop();
// 打印弹出顶点的 SCC
if (visited[v] == false) {
gr.DFSUtil(v, visited);
cout << endl;
}
}
}
// 驱动程序代码
int main() {
// 给定图
Graph g(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(2, 4);
// 函数调用以查找 SCC
// 使用 Kosaraju 算法
g.printSCCs();
return 0;
}
输出
0 1 2 4 3
结论
总之，Tarjan 和 Kosaraju 方法的时间复杂度为 O(V + E)，其中 V 表示图中的顶点集，E 表示图中的边集。Tarjan 算法中的常数因子明显低于 Kosaraju 方法中的常数因子。Kosaraju 方法至少遍历图两次，因此常数因子可能是双倍时间。我们可以使用 Kosaraju 的方法生成现在处于活动状态的 SCC，同时完成第二个 DFS。找到 SCCs 子树的头部后，使用 Tarjan 算法打印 SCC 需要更长的时间。
虽然两种方法的线性时间复杂度相同，但在用于 SCC 计算的方法或流程方面存在一些差异。虽然 Kosaraju 的技术在图上运行两次 DFS(如果我们希望保持原始图不变，则运行三次 DFS)，并且与确定图的拓扑顺序的方法非常相似，但 Tarjan 的方法仅依赖 DFS 中的节点记录来对图进行分区。
