Strong Connectivity in Graphs

Strong Connectivity is a thing we use only in directed graphs. Definition of Directed Graphs HERE

Def

Nodes a and b in a graph are mutually reachable if there is both a path from a to b and also a path from b to a. If all the nodes in the graph are mutually reachable in directed graph it is strongly connected .

Lemma. Let s be any node in graph G, Graph G is strongly connected if and only if (iff) s is reachable from every other node and every node is reachable from s.

Strong Connectivity
Strongly Connected Graph

How to determine strong connectivity in Graph?

Time Complexity: O(m+n)

  • Pick any node s
  • Run BFS from s in G. (BFS: Breadth First Search . Definition HERE)
  • Check that s reaches all other nodes or not.
  • Now reverse the Edges in the Graph ( Head becomes Tail and Tail becomes Head)
  • Run BFS again on the reversed Graph.
  • if s reaches all the nodes in graph G and graph G-reversed.
  • then Strongly connected graph is G.
Strong Connectivity
You can Reach any Node from any other Node in this graph

Strong Component

A strong component is maximal subset of mutually reachable nodes. For example there is a large graph having nodes from a-f and the graph is not strongly connected. In the graph there may be three nodes, suppose a-c which are mutually reachable from each other. So a-c is strong component in graph a-f.

How to find Strong Components in Graph?

Time Complexity: O(m+n)

  • Pick any node a
  • Run DFS from s in G. (DFS: Depth First Search . Definition HERE)
  • Now reverse the Edges in the Graph ( Head becomes Tail and Tail becomes Head)
  • Run DFS again on the reversed Graph. But start from the node which was last in Previous DFS.
  • Output the forest formed by both the DFS iterations. If both contain same nodes they are strong component.

READ MORE

Algorithms related posts visit HERE

Data Structures related posts visit HERE

Databases related posts Visit HERE

Python-related posts Visit HERE

C++ related posts Visit HERE

Data Science related posts visit HERE

Leave a Comment