Tarjan演算法和Kosaraju演算法的比較
- WBOY轉載
- 2023-09-04 19:17:14837瀏覽
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 對圖進行分區。
以上是Tarjan演算法和Kosaraju演算法的比較的詳細內容。更多資訊請關注PHP中文網其他相關文章！