数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学Tarjan算法和Kosaraju算法的比较
Tarjan算法用于在有向图中查找强连通分量。Robert Tarjan在1972年创建了这种图遍历技术。它使用深度优先搜索和栈数据结构有效地找到并处理每个强连通分量，而无需访问已处理的节点。该算法广泛应用于计算机科学和图论中，具有多种应用，包括算法设计、网络分析和数据挖掘。
Kosaraju算法对图进行两次遍历。第一次遍历以逆序遍历图，并为每个节点分配一个“完成时间”。第二次遍历按照节点的完成时间顺序访问节点，并识别和标记每个强连通分量。
Tarjan算法方法
在这个例子中，Graph类在程序开始时定义，其构造函数根据图中的顶点数初始化邻接表数组。addEdge函数通过将目标顶点添加到源顶点的邻接表中来添加边到图中。
程序的核心是SCCUtil方法，这是一个基于递归深度优先搜索的函数，由SCC方法调用来查找强连通分量。该函数接收当前顶点u、发现时间数组disc、低值数组low、顶点栈数组st和布尔值数组stackMember（跟踪顶点是否在栈中）作为输入。
该方法首先为当前顶点分配发现时间和低值，然后将当前顶点压入栈中，并将它的stackMember值设置为true。然后，它递归地更新所有相邻顶点的低值到当前顶点。
该方法迭代地访问未发现的顶点v，并根据v是否已经在栈中更新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
结论
总之，Tarjan算法和Kosaraju算法的时间复杂度均为O(V + E)，其中V表示图中顶点的集合，E表示图中边的集合。Tarjan算法中的常数因子远小于Kosaraju算法。Kosaraju算法至少遍历图两次，因此常数因子可能为两倍。我们可以使用Kosaraju算法来生成当前活动的SCC，同时完成第二次DFS。使用Tarjan算法打印SCC需要更长的时间，一旦找到SCCs子树的头节点。
尽管这两种算法的时间复杂度都是线性的，但在用于计算SCC的方法或过程中存在一些差异。Kosaraju算法在图上运行两次DFS（如果我们希望保持原始图不变，则为三次DFS），这与确定图的拓扑排序的方法非常相似，而Tarjan算法只依赖于DFS中节点的记录来划分图。
浏览量：509
