Do you think IIT Guwahati certified course can help you in your career?
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.
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.
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.
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.
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.
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.
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).
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.
24+ registered 
