卓越飞翔博客
Tarjan 算法是在有向图中定位强链接组件，Robert Tarjan 在 1972 年创建了称为 Tarjan 算法的图遍历技术。它无需遍历先前处理的节点，而是使用深度有效地定位和处理每个高度相关的组件首先是搜索策略和栈数据结构。该算法经常用于计算机科学和图论，并具有多种用途，包括算法创建、网络分析和数据挖掘。
Kosaraju 的算法由对图的两次遍历组成。在第一遍中，以相反的顺序遍历图，并为每个节点分配“完成时间”。在第二遍中，按照节点的完成时间顺序访问节点，并识别和标记每个强连接组件。
Tarjan算法方法
在本例中，Graph 类在程序开头定义，其构造函数根据图中的顶点数初始化邻接表数组。通过将目标顶点包含在源顶点的邻接列表中，addEdge 函数向图中添加一条边。
SCCUtil 方法是 SCC 方法用来发现 SCC 的基于 DFS 的递归函数，它构成了该程序的基础。当前顶点u、发现时间disc的数组、低值low的数组、顶点堆栈st的数组以及跟踪顶点是否在堆栈中的布尔值数组stackMember是该函数的输入。
该过程将当前顶点放入堆栈，并在首先为其分配发现时间和低值后将其 stackMember 值更改为 true。之后，它以递归的方式将所有附近顶点的低值更新到当前顶点。
该技术迭代地访问未发现的顶点 vs 并修改 u 的低值。如果v已经在堆栈中，该方法根据v的发现时间修改u的低值。
Tarjan算法
初始化算法
开始遍历图表
检查强连接组件
重复直到所有节点都被访问过
返回强连通分量
该方法将所有顶点从堆栈中弹出，直到当前顶点 u 被弹出，打印弹出的顶点，如果 u 是头节点（即，如果其低值等于其发现时间），则将其 stackMember 值设置为 false。
示例
'// C++ program to find the SCC using
// Tarjan's algorithm (single DFS)
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
// A class that represents
// an directed graph
class Graph {
// No. of vertices
int V;
// A dynamic array of adjacency lists
list<int>* adj;
// A Recursive DFS based function
// used by SCC()
void SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]);
public:
// Member functions
Graph(int V);
void addEdge(int v, int w);
void SCC();
};
// Constructor
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// Function to add an edge to the graph
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
// Recursive function to finds the SCC
// using DFS traversal
void Graph::SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]) {
static int time = 0;
// Initialize discovery time
// and low value
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;
// Go through all vertices
// adjacent to this
list<int>::iterator i;
for (i = adj[u].begin();
i != adj[u].end(); ++i) {
// v is current adjacent of 'u'
int v = *i;
// If v is not visited yet,
// then recur for it
if (disc[v] == -1) {
SCCUtil(v, disc, low, st, stackMember);
// Check if the subtree rooted
// with 'v' has connection to
// one of the ancestors of 'u'
low[u] = min(low[u], low[v]);
}
// Update low value of 'u' only of
// 'v' is still in stack
else if (stackMember[v] == true)
low[u] = min(low[u], disc[v]);
}
// head node found, pop the stack
// and print an SCC
// Store stack extracted vertices
int w = 0;
// If low[u] and disc[u]
if (low[u] == disc[u]) {
// Until stack st is empty
while (st->top() != u) {
w = (int)st->top();
// Print the node
cout << w << " ";
stackMember[w] = false;
st->pop();
}
w = (int)st->top();
cout << w << "n";
stackMember[w] = false;
st->pop();
}
}
// Function to find the SCC in the graph
void Graph::SCC() {
// Stores the discovery times of
// the nodes
int* disc = new int[V];
// Stores the nodes with least
// discovery time
int* low = new int[V];
// Checks whether a node is in
// the stack or not
bool* stackMember = new bool[V];
// Stores all the connected ancestors
stack<int>* st = new stack<int>();
// Initialize disc and low,
// and stackMember arrays
for (int i = 0; i < V; i++) {
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}
// Recursive helper function to
// find the SCC in DFS tree with
// vertex 'i'
for (int i = 0; i < V; i++) {
// If current node is not
// yet visited
if (disc[i] == NIL) {
SCCUtil(i, disc, low, st, stackMember);
}
}
}
// Driver Code
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);
// Function Call to find SCC using
// Tarjan's Algorithm
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 Visited[, stack& Stack], int v) 将顶点按照其完成时间的顺序添加到堆栈中。
示例 2
'// C++ program to print the SCC of the
// graph using Kosaraju's Algorithm
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
// No. of vertices
int V;
// An array of adjacency lists
list<int>* adj;
// Member Functions
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();
};
// Constructor of class
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// Recursive function to print DFS
// starting from v
void Graph::DFSUtil(int v, bool visited[]) {
// Mark the current node as
// visited and print it
visited[v] = true;
cout << v <<" ";
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
// Traverse Adjacency List of node v
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// If child node *i is unvisited
if (!visited[*i])
DFSUtil(*i, visited);
}
}
// Function to get the transpose of
// the given graph
Graph Graph::getTranspose() {
Graph g(V);
for (int v = 0; v < V; v++) {
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// Add to adjacency list
g.adj[*i].push_back(v);
}
}
// Return the reversed graph
return g;
}
// Function to add an Edge to the given
// graph
void Graph::addEdge(int v, int w) {
// Add w to v’s list
adj[v].push_back(w);
}
// Function that fills stack with vertices
// in increasing order of finishing times
void Graph::fillOrder(int v, bool visited[],
stack<int>& Stack) {
// Mark the current node as
// visited and print it
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// If child node *i is unvisited
if (!visited[*i]) {
fillOrder(*i, visited, Stack);
}
}
// All vertices reachable from v
// are processed by now, push v
Stack.push(v);
}
// Function that finds and prints all
// strongly connected components
void Graph::printSCCs() {
stack<int> Stack;
// Mark all the vertices as
// not visited (For first DFS)
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Fill vertices in stack according
// to their finishing times
for (int i = 0; i < V; i++)
if (visited[i] == false)
fillOrder(i, visited, Stack);
// Create a reversed graph
Graph gr = getTranspose();
// Mark all the vertices as not
// visited (For second DFS)
for (int i = 0; i < V; i++)
visited[i] = false;
// Now process all vertices in
// order defined by Stack
while (Stack.empty() == false) {
// Pop a vertex from stack
int v = Stack.top();
Stack.pop();
// Print SCC of the popped vertex
if (visited[v] == false) {
gr.DFSUtil(v, visited);
cout << endl;
}
}
}
// Driver Code
int main() {
// Given Graph
Graph g(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(2, 4);
// Function Call to find the SCC
// using Kosaraju's Algorithm
g.printSCCs();
return 0;
}
输出
'0 1 2
4
3<p></p>结论
总之，Tarjan 和 Kosaraju 方法的时间复杂度为 O(V + E)，其中 V 表示图中的顶点集，E 表示图中的边集。 Tarjan 算法中的常数因子明显低于 Kosaraju 方法中的常数因子。 Kosaraju 的方法至少遍历该图两次，因此常数因子可能是两倍。当我们完成第二个 DFS 时，我们可以使用 Kosaraju 的方法来生成现在处于活动状态的 SCC。一旦找到 SCC 子树的头部，用 Tarjan 算法打印 SCC 需要更长的时间。
尽管两种方法的线性时间复杂度相同，但 SCC 计算所使用的方法或流程存在一些差异。虽然 Kosaraju 的技术在图上运行两个 DFS（如果我们希望保持原始图不被修改，则运行三个 DFS），并且与确定图的拓扑排序的方法非常相似，但 Tarjan 的方法仅依赖于节点记录DFS 对图进行分区。
