Strongly Connected Components in A Graph Using Tarjan Algorithm

See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/295010370
Strongly Connected Components in a Graph using Tarjan Algorithm
Raw Data · April 2015

DOI: 10.13140/RG.2.1.4180.2002
CITATIONS READS
0 1,215
1 author:
Syed aqeel Awais

The University of Winnipeg
5 PUBLICATIONS 2 CITATIONS
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
Descriptive approach to quantify the similarity of graphs View project
All content following this page was uploaded by Syed aqeel Awais on 18 February 2016.
The user has requested enhancement of the downloaded file.

Advanced
Algorithms
Design
Strongly Connected
Components in a graph
Syed Aqeel Awais

Student# 3059614
1. Strong Connectivity
Definition: Let G be a directed graph. Suppose that for each pair of vertices v,w in G,
there exists a path p1: v w and p2: w v. Then G is said to be strongly connected. [1]
Lemma: Let G=(v,e) be a directed graph. We may define an equivalence relation on the
set of vertices as follows: two vertices v and w are equivalent if there is a closed path
p: v v which contains w. Let the distinct equivalence classes under this relation be vi ,
1<=i<=n. Let Gi= (vi,ei) where ei ={(v,w)  e|v,wvi}.
I. Each Gi is strongly connected
II. No Gi is a proper subgraph of a strongly connected subgraph of G. [1]
A graph can be defined as the combination of vertices and the edges associated
between them.
G= (V, E)
Where V is the number of vertices and E represents the edges. Generally A directed can
be seen as below in figure,[2]
Figure 1: Directed Graph

Edges can be classified into four different types.
• Tree edge: in the depth-first forest. Found by exploring (u, v).
• Back edge: (u, v), where u is a descendant of v (in the depth-first tree).
• Forward edge: (u, v), where v is a descendant of u, but not a tree edge.
• Cross edge: any other edge (u, v) such that u is not a descendant of v and vice versa. [2]
They can be seen clearly from the below image,
Figure 2: Different Types of Edges
2. Representation of Graphs
Graphs can be represented in two ways by using the adjacency matrix and the lists. In
this project link list have been used for checking the adjacency between different nodes.
The list can be represented as follows, [2]
3. Algorithm Description
BEGIN
INTEGER i;
PROCEDURE STRONGCONNECT (v);
BEGIN
LOWLINK (v) := NUMBER (v) :=i :=i + 1;
put v on stack of points;
FOR w in the adjacency list of v DO
BEGIN
IF w is not yet numbered THEN

BEGIN comment (v, w) is a tree arc;
STRONGCONNECT (w);
LOWLINK (v) := min (LOWLINK (v),LOWLINK (w));
END
ELSE IF NUMBER (w) < NUMBER (v) DO
BEGIN comment (v, w) is a frond or cross-link;
if w is on stack of points THEN
LOWLINK (v) := min (LOWLINK (v), NUMBER (w));
END;
END;
If (LOWLINK (v) = NUMBER (v)) THEN

BEGIN comment v is the root of a component;
start new strongly connected component;
WHILE w on top of point stack satisfies
NUMBER (w) >=NUMBER (v) DO
delete w from point stack and put w in current component
END;
END;
I:=0;
empty stack of points;
FOR w a vertex IF w is not yet numbered THEN STRONGCONNECT (w);
END;
4. Time Analysis
The time required by algorithm is linear in space and time. When the search has been
started, the values of the LOWLINK has been evaluated and for every search the found
vertex has been placed on the stack data structure and this has been removed only once
from the stack. A Boolean array has been used for checking if the found vertex is already
visited or not. As every operation has been done once, the strongly connected
component algorithm is linearly bound in both the space and time (|V| + |E|). [1]
5. Implementation
A link list has been considered for checking the adjacency of different vertices with each
other. First, we declare an object for the graph class and initialized the constructor with
given number of vertices.
In the first graph we have entered five vertices and traverse over all of them using the
link list, list<int> *adj,
Now we push this vertex into the stack to store this value, stack<int>*st and push this
value as st->push(u). The next step is to check the adjacency with this vertex by
traversing the whole link list as adj[u].begin to the adj[u].end. Moreover, the vertices
which are adjacent to each other add an edge between them using the function
addedge,
We have kept Boolean array “bool stackmember[]” for checking if the vertex has already
been visited in the stack or not which makes it very fast checking for the visited and unvisited
vertices and to keep track on them.
If the vertex is not already a stack member, we just keep on adding the tree edges between
them and the low value of the vertex would be defined as,
Low[u] = min ( low[u], low[v] )
If the vertex has already been visited then the back edge has been added and the low value of
the is defined as per it is defined in the tarjan’s algorithm,
Low[u] = min (low[u] , num[v])
As we move ahead we use the recursive function for finding the adjacency as deep as possible
and found the vertices as below,
The strongly connected components are:
The First strongly connected component: 2
The second strongly connected component: 1
The third strongly connected component: 4 3 0
Another graph is provided for finding the strongly connected components in that graph,
The values which has same values of low link has formed the strongly connected
component.
The First Strongly Connected component is: 1

The second Strongly Connected component is: 0
The third Strongly Connected component is: 2
The fourth Strongly Connected component is: 6
The Fifth Strongly Connected component is: 5 4 3
The next graph which has been considered is,
The First Strongly Connected Component: 3 4
The Second Strongly Connected Component: 0 1 2
References:
1. Tarjan, Robert. "Depth-first search and linear graph algorithms." SIAM journal on computing 1,
no. 2 (1972): 146-160.
2. Lecture Slides
View publication stats

Strongly Connected Components in A Graph Using Tarjan Algorithm

Uploaded by

Copyright:

Available Formats

Strongly Connected Components in A Graph Using Tarjan Algorithm

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Strongly Connected Components in A Graph Using Tarjan Algorithm

Uploaded by

Copyright:

Available Formats

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

Strongly Connected Components in a Graph using Tarjan Algorithm

Raw Data · April 2015

Syed aqeel Awais

Descriptive approach to quantify the similarity of graphs View project

The user has requested enhancement of the downloaded file.

Syed Aqeel Awais

Figure 1: Directed Graph

Figure 2: Different Types of Edges

IF w is not yet numbered THEN

If (LOWLINK (v) = NUMBER (v)) THEN

Low[u] = min ( low[u], low[v] )

Low[u] = min (low[u] , num[v])

The First strongly connected component: 2

The second strongly connected component: 1

The third strongly connected component: 4 3 0

The First Strongly Connected component is: 1

View publication stats

You might also like