資料結構
網路
關係資料庫管理系統 (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
