Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Articulation points and bridges
3.
Bridge,
4.
Point of Articulation
5.
Tarjan's Algorithm
5.1.
First Step
5.2.
Second Step
5.3.
Third Step 
6.
Algorithm
7.
Implementation in C++
7.1.
Output
8.
Implementation in Python
8.1.
Output
9.
Complexity Analysis for both Language
9.1.
Time Complexity:
9.2.
Auxiliary Space
10.
Frequently Asked Questions
10.1.
How does Tarjan's algorithm function?
10.2.
Which approach can locate components in a network that are tightly connected?
10.3.
How do you tell if a graph component is tightly connected?
10.4.
What does it imply when something is highly connected?
10.5.
How do you determine whether a graph has strong connections?
11.
Conclusion
Last Updated: Mar 27, 2024
Hard

Tarjan’s Algorithm to find Strongly Connected Components

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Here, we'll examine Tarjan's algorithm. Tarjan's Technique is a useful graph approach for locating the highly related components of a directed graph in linear time by utilising Depth First Search traversal of a network. Strongly linked component nodes create a subtree in the graph's DFS Algorithm spanning tree, which is the central concept used.We shall examine Tarjan’s Algorithm in this part.

Introduction

Articulation points and bridges

In Graph Theory, bridges and articulation points are significant because, in practical applications, they frequently indicate weak areas, bottlenecks, or weaknesses in the graph.

Consequently, it's essential to locate and identify where and when they happen quickly. This will help Tarjan’s Algorithm.

Bridge,

Bridges have a red backdrop because eliminating any one of them causes the graph to be split in half. It'll be beneficial for Tarjan's Algorithm.

Bridge & Point of Articulation
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Point of Articulation

The nodes highlighted in orange indicate articulation points because, if any of them were removed, the graph would split into two halves.

Tarjan's Algorithm

This algorithm will be explained in below steps:

First Step

Do a Depth First Search (DFS) traverse starting at any node, tagging each node with a higher id value as you proceed.

First Step

Second Step

When doing a Depth First Search (DFS), a node's Low Link Value is the least id it can reach, not including itself.

Record the least low link value and each node's ID.

All low link variables can be initially initialised to the corresponding node id.

There is a path connecting the first and second nodes to node 0 if we look at the first and second nodes. Therefore, we must set the first node's and the second node's low link values to zero node.

Link values to zero node

However, because there isn't another node they can reach with a lesser id, nodes third, fourth, and fifth are already at their ideal low link value.

Second step

There is a route from node sixth, node seventh, and node eighth, respectively, to node fifth.

Therefore, we need to change the low link values for node sixth, node seventh, and node eighth to node fifth.

Second step after changing node

Third Step 

Bridges will be discovered during the Depth First Search if the id of the node from which your edge is coming is smaller than the low link value of the node to which your edge is heading (DFS).

Third Step

Algorithm

Tarjan’s Algorithm uses the graph's DFS spanning tree's characteristic that highly linked component nodes create a subtree. 

The actions involved are:

  • The SCC subtrees are deleted from the nodes and recorded when they are encountered using a DFS performed over them.
     
  • For every user, two values—Depth First Search_num(u) and Depth First Search_low(u) are kept. When the node u is first investigated, the counter's value is Depth First Search_num(u). The lowest Depth First Search num that may be reached from u and is not a part of another SCC is stored by Depth First Search low(u).
     
  • The nodes are placed onto a stack as they are investigated.
     
  • A node's undiscovered children are investigated, and Depth First Search low(u) is updated.​​
     
  • The first investigated node in a node's highly connected component is one with Depth First Search_low(u) == Depth First Search_num(u), and all nodes above it in the stack are popped out and given the appropriate SCC number.

Implementation in C++

//Tarjan's Algorithm
#include<iostream>

#include<stack>

#define NODE 8
using namespace std;
int generated_graph[NODE][NODE] = {
  {0, 0, 1, 0, 0, 0, 0, 0},
  {1, 0, 0, 0, 0, 0, 0, 0},
  {0, 1, 0, 1, 0, 0, 0, 0},
  {0, 0, 0, 0, 1, 0, 0, 0},
  {0, 0, 0, 0, 0, 1, 0, 0},
  {0, 0, 0, 0, 0, 0, 1, 0},
  {0, 0, 0, 0, 0, 0, 0, 1},
  {0, 0, 0, 0, 1, 0, 0, 0}
};
int min(int a, int b) {
    return (a < b) ? a : b;
}
void find_Component(int u, int tuple_disc[], int tuple_low[], stack < int > & created_stack, bool stack_Item[]) {
    static int time = 0;

    //discovery time and low value initially is 1
    tuple_disc[u] = tuple_low[u] = ++time;
    created_stack.push(u);

    //as (u) in the stack flagged
    stack_Item[u] = true;
    for (int v = 0; v < NODE; v++) {

        if (generated_graph[u][v]) {
            if (tuple_disc[v] == -1) {

                //if v is not reached
                find_Component(v, tuple_disc, tuple_low, created_stack, stack_Item);

                //Update tuple_low for u while v is in the stack.
                tuple_low[u] = min(tuple_low[u], tuple_low[v]);
            } else
            if (stack_Item[v])
                tuple_low[u] = min(tuple_low[u], tuple_disc[v]);
        }
    }
    int popped_Item = 0;
    if (tuple_low[u] == tuple_disc[u]) {
        while (created_stack.top() != u) {
            popped_Item = created_stack.top();
            cout << popped_Item << " ";
            stack_Item[popped_Item] = false;

            //indicate the object as popped
            created_stack.pop();
        }
        popped_Item = created_stack.top();
        cout << popped_Item << endl;
        stack_Item[popped_Item] = false;
        created_stack.pop();
    }
}
void function_strong_Component() {
    int tuple_disc[NODE], tuple_low[NODE];
    bool stack_Item[NODE];
    stack < int > created_stack;
    for (int i = 0; i < NODE; i++) {

        //initialise each component
        tuple_disc[i] = tuple_low[i] = -1;
        stack_Item[i] = false;
    }
    for (int i = 0; i < NODE; i++)

        //initialise each component
        if (tuple_disc[i] == -1)
            find_Component(i, tuple_disc, tuple_low, created_stack, stack_Item);
}
int main() {
    function_strong_Component();
}

Output

7 6 5 4
3
1 2 0

Implementation in Python

# Tarjan's Algorithm

from collections import defaultdict

# This class uses an adjacency
# list representation to represent
# a directed graph.
class Graph:
    def __init__(direct, vertices):

        # vertices
        direct.V = vertices

        direct.graph = defaultdict(list)
        direct.Time = 0

    # graphing function to add edges
    def add_Edge(direct, u, v):
        direct.graph[u].append(v)

    def find_Component(direct, u, tuple_low, tuple_disc, created_stack, st):

        # Set the tuple_discovery time and tuple_low value initials
        tuple_disc[u] = direct.Time
        tuple_low[u] = direct.Time
        direct.Time = 1
        created_stack[u] = True
        st.append(u)

        # Walk around all of the vertices nearby.
        for v in direct.graph[u]:

            # Recur for v if it hasn't been seen yet.
            if tuple_disc[v] == -1:

                direct.find_Component(v, tuple_low, tuple_disc, created_stack, st)

                tuple_low[u] = min(tuple_low[u], tuple_low[v])

            elif created_stack[v] == True:

                tuple_low[u] = min(tuple_low[u], tuple_disc[v])
        w = -1

        # To keep stack extracted vertices in storage
        if tuple_low[u] == tuple_disc[u]:
            while w != u:
                w = st.pop()
                print(w, end=" ")
                created_stack[w] = False

            print()

    # DFS traversal.
    def function_strong_Component(direct):
        tuple_disc = [-1] * (direct.V)
        tuple_low = [-1] * (direct.V)
        created_stack = [False] * (direct.V)
        st = []

        # Recursive helper function should be invoked.
        for i in range(direct.V):
            if tuple_disc[i] == -1:
                direct.find_Component(i, tuple_low, tuple_disc, created_stack, st)

# Make the graph shown in the illustration above.
generated_graph = Graph(5)
generated_graph.add_Edge(1, 0)
generated_graph.add_Edge(0, 2)
generated_graph.add_Edge(2, 1)
generated_graph.add_Edge(0, 3)
generated_graph.add_Edge(3, 4)

generated_graph.function_strong_Component()

Output

4 
3 
1 2 0 

Complexity Analysis for both Language

Time Complexity:

O(V+E), where V is the number of graph vertices, and E denotes the number of edge nodes.

Explanation:

We are essentially traversing the graph using a Single DFS algorithm. As a result, each node is only ever visited once. We operate consistently on each node's adjacency list for a certain number of iterations. Time complexity will thus be O(V+E).

Auxiliary Space

O(V), where V is the number of graph vertices.

Explanation: 

The maximum we can store in our map, stack, and arrays is the total number of vertices in the graph. Space complexity thus is O(V).

Frequently Asked Questions

How does Tarjan's algorithm function?

Tarjan's Algorithm to Find Strongly Connected Components Illustration

By leveraging Depth First Search traversal of a network, Tarjan's Algorithm is an effective graph algorithm for finding the strongly linked components in a directed graph in linear time. Strongly linked component nodes create a subtree in the graph's DFS spanning tree, exploiting the main concept.

Which approach can locate components in a network that are tightly connected?

Finding the strongly connected components (SCCs) of a directed graph may be done using Tarjan's Algorithm for strongly connected components. As an alternate technique, it matches the time constraint for Kosaraju's algorithm and the path-based strong component algorithm since it runs in linear time.

How do you tell if a graph component is tightly connected?

A directed graph is said to be highly linked if there is a path connecting each pair of the graph's vertices in each direction. The first vertex in the pair has a path leading to the second, and the second vertex has a path leading to the first.

What does it imply when something is highly connected?

Strongly connected components (SCCs) are directed graphs or parts of directed graphs in which every vertex and every node may be reached from every other vertex through a path.

How do you determine whether a graph has strong connections?

Conducting a Depth-first search (DFS) or a Breadth-first search (BFS) beginning at each graph vertex is a straightforward solution. The graph is tightly linked if each DFS/BFS call reaches every other vertex in the graph.

Conclusion

That concludes the tutorial of Tarjan’s Algorithm. for a better understanding, check out the various examples and run the code in your C++ Compiler.

Check out these questions. It will help you in exploring path-finding algorithms similar to Tarjan’s Algorithm.
 

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Comment here with any questions or concerns you may have about the post.

Happy Learning Ninja! 🥷

Previous article
Maximize Difference between pair of Nodes in a given rooted Tree such that one Node is Ancestor of another
Next article
Red-Black Trees Top-Down Insertion
Live masterclass