DEV Community

Cover image for Strong Connectivity in Graphs
He Codes IT
He Codes IT

Posted on

Strong Connectivity in Graphs

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

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.


Discussion (0)