Things we will discuss

Things we will discuss

• Introduction
• Strongly Connected Components
• Kosaraju's algorithm to compute strongly connected components in a directed graph
• Practice Problems

Prerequisite:

• Topological Sorting
• Connected Component

Introduction

In a directed graph, the edges can be traversed in one direction only, so even if the graph is connected, this does not guarantee that there would be a path from a node to another. For this reason, it is meaningful to define a new concept that requires more than connectivity.

Strongly connected components

A directed graph G(V, E) is said to be strongly connected if and only if there is a directed path b/w any two vertices, that is, for every pair of vertices u and v there is a path from u to v and v to u.
For example, in the below picture in the graph (b) we have a path between each pair of vertices and in the graph (a) we don't have a path between 2 to node 1

The Strongly connected components of a graph divide the graph into strongly connected parts that are as large as possible. The strongly connected components form an acyclic component graph that represents the deep structure of the original graph.

Defining Strongly Connected Component Mathematically:

The strongly connected components of a directed graph G is a partition of the vertices into maximal subsets such that each subset is strongly connected, that is, there is a path from u to v and v to u for all u, v ∈ V.

For example, for the graph,

The Strongly Connected Components are as follows:

{ v1 }, { v2, v4, v3 }, { v6 }, { v5, v8, v7 }

Component graph

The strongly connected components form an acyclic component graph which represents the deep structure of the original graph. components are
A = { v1 }
B = { v2, v4, v3 }
C = { v6 }
D = { V5, v8, v7 }

Kosaraju's Algorithm: Computing Strongly Connected Components of Directed Graph

Kosaraju's algorithm is an efficient method for finding the strongly connected components of a directed graph. The algorithm performs tow depth-first searches: The first search constructs a list of nodes according to the structure of the graph, and the second search forms the. strongly connected components.

Search 1

The first phase of Kosaraju's algorithm constructs a list of nodes in the order in which a depth-first search process them. The algorithm goes through the nodes and begins a DFS at each unprocessed node and each node will be added to the list after it has been processed as we have done to Topological Sort.

In the example graph, the nodes are processed in the following order:

The notation (x/y)  means that the processing of the node started at time x and finished at time y. Thus the corresponding list is as follows:

Search 2

The second phase of the algorithm forms the strongly connected components of the graph. First, the algorithm reverses every edge in the graph and gets the Transpose of the Graph i.e. for node u,v in the graph G we have node v,u in graph GT (Transpose Graph).

This guarantees that during the second search, we will always find strongly connected components that do not have extra nodes.

Transpose Graph:

After this, the algorithm goes through the list of nodes created by the first search i.e. in topological order. If a node does not belong to a component, the algorithm creates a new component and starts a depth-first search that adds all-new nodes found during the search to a new component.

In the example graphs, these are 4 strongly connected components.

Note that since all edges are reversed, the component does not "leak" to other parts in the graph.

Implementation in C++

Practice Problems

1. Checkpost ( 427C )
2. Ralph and Mushrooms ( 894E )
3. Scheme ( 22E )

That's all for this article, in the next session we will be discussing Tree Queries and problems related to it and for now practice problems. ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA