1 votes 1 votes 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. Graph Theory graph-theory discrete-mathematics algorithms + – Chhotu asked Nov 10, 2017 • edited Nov 10, 2017 by Chhotu Chhotu 7.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply royal shubham commented Jan 26, 2019 reply Follow Share yes any1 have short method to find it quickly then pls answer it . 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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/ saurav raghaw answered Feb 22, 2019 • edited Feb 22, 2019 by saurav raghaw saurav raghaw comment Share Follow See all 0 reply Please log in or register to add a comment.