Comparison of Tarjan algorithm and Kosaraju algorithm-C++-php.cn

Comparison of Tarjan algorithm and Kosaraju algorithm

Tarjan’s algorithm is a graph traversal technique called Tarjan’s algorithm created by Robert Tarjan in 1972 for locating strongly linked components in a directed graph. Instead of traversing previously processed nodes, it efficiently locates and processes each highly relevant component using depth-first search strategies and stack data structures. The algorithm is frequently used in computer science and graph theory and has a variety of uses, including algorithm creation, network analysis, and data mining.

Kosaraju's algorithm consists of two traversals of the graph. In the first pass, the graph is traversed in reverse order and each node is assigned a "completion time". In the second pass, nodes are visited in order of their completion time and each strongly connected component is identified and labeled.

Tarjan algorithm method

In this example, the Graph class is defined at the beginning of the program, and its constructor initializes the adjacency list array based on the number of vertices in the graph. The addEdge function adds an edge to the graph by including the target vertex in the adjacency list of the source vertex.

The SCCUtil method is a DFS-based recursive function used by the SCC method to discover SCCs, and it forms the basis of this program. The current vertex u, an array of discovery times disc, an array of low values low, an array of vertex stack st, and stackMember, an array of Boolean values that keeps track of whether a vertex is on the stack, are the inputs to this function.

This procedure puts the current vertex on the stack and changes its stackMember value to true after first assigning it a discovery time and a low value. After that, it recursively updates the low values of all nearby vertices to the current vertex.

This technique iteratively visits undiscovered vertices vs and modifies low values of u. If v is already on the stack, this method modifies the lower value of u based on the time v was discovered.

Tarjan algorithm

Initialization algorithm
Start traversing the chart
Check strong connection components
Repeat until all nodes have been visited
Return strongly connected components

This method pops all vertices from the stack until the current vertex u is popped, prints the popped vertex, and if u is the head node (that is, if its low value is equal to its discovery time), set its stackMember value to false.

Example

// 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;
}

Copy after login

Output

Copy after login

Method 2-Kosaraju

Kosaraju algorithm

Create a collection of visited nodes and an empty stack at startup.
Start a depth-first search from the first node in the graph that has not been visited yet. Push each node visited throughout the search onto the stack.
The direction of each graphic edge should be reversed.
If the stack is still full of nodes, pop the nodes from the stack. If the node has not been visited, a depth-first search is performed from that node. Mark each node visited during the search as a member of the current highly linked component.
Repeat until all nodes have been visited
Each highly interconnected component will be identified and annotated at the end of the program.

The following C code uses Kosaraju's algorithm to find strongly connected components (SCC) in a directed graph. The software defines a class named Graph, which has the following member functions:

Graph(int V): Constructor, input the number of vertices V and initialize the adjacency list of the graph.

Void addEdge(int v, int w): Using two integers v and w as input, this method creates an edge connecting vertex v to vertex w in the graph.

void printSCCs() function uses Kosaraju algorithm to print each SCC in the graph.

Graph getTranspose() method provides the transposition of the graph.

Use the recursive function void fillOrder(int v, bool Visited[, stack& Stack], int v) to add vertices to the stack in the order of their completion time.

Example 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; 
}

Copy after login

Output

0 1 2 
4
3</p><p>

Copy after login

in conclusion

In summary, the time complexity of Tarjan and Kosaraju's method is O(V E), where V represents the set of vertices in the graph and E represents the set of edges in the graph. The constant factors in Tarjan's algorithm are significantly lower than those in Kosaraju's method. Kosaraju's method traverses the graph at least twice, so the constant factor is probably twice as high. When we complete the second DFS, we can use Kosaraju's method to generate the now active SCC. Once the head of the SCC subtree is found, printing the SCC with the Tarjan algorithm takes longer.

Although the linear time complexity of the two methods is the same, there are some differences in the methods or processes used for SCC calculations. While Kosaraju's technique runs two DFS on the graph (or three DFS if we wish to keep the original graph unmodified) and is very similar to the method of determining the topological ordering of a graph, Tarjan's method relies only on node records DFS partitions the graph.

The above is the detailed content of Comparison of Tarjan algorithm and Kosaraju algorithm. For more information, please follow other related articles on the PHP Chinese website!