# 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.

#### 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 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.