Strongly Connected, Unilaterally connected and weakly Connected

Question

Hi Guys,

Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ?

For Example - If  1 dead point then graph is Unilaterally Connected and If  2 dead points then graph is Weakly Connected.

Comments

yes any1 have short method to find it quickly then pls answer it .

Answer 1

Strongly connected graph: A directed graph is said to be strongly connected if for any pair of nodes there is a path from each one to the other. That means there is a route between every two nodes.

Strongly connected graph: 

 

in this directed Graph there is a path between every pair of vertices, so it is a strongly connected graph.

Unilaterally connected graph: A directed graph is said to be unilaterally connected if for any pair of nodes at least one of the nodes is reachable from the other. That means a directed graph is unilaterally connected if, for any two vertices A and B, there is a directed path from A to B or from B to A, but not necessarily both (although there could be).

Strongly connected implies that both directed paths exist. This means that strongly connected graphs are a subset of unilaterally connected graphs.

 

Unilaterally connected graph: here we can see, there is a path between C to B, there is no path between B to C.

Weakly connected Graph: A directed graph is weakly connected if it's underlying graph (means graph without direction) is connected. ​​​​​​​ 

Check if a graph is strongly connected(Kosaraju using DFS) https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

Strongly Connected Components https://www.geeksforgeeks.org/strongly-connected-components/

Tarjan’s Algorithm to find Strongly Connected Components https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/