Pairs with vertices inaccessible to each other in a straight diagram
I am asked to develop an algorithm to determine if there is any pair of vertices unreachable from each other in a directed graph. The algorithm should be executed in O (| V | + | E |) mode
Meaning: vertex i cannot reach vertex j, and vertex j cannot reach vertex i.
I read about a method for finding strongly related components, I wonder if I can start from there and develop an algorithm that can be used under the current circumstances?
source to share
If you can find all the strongly coupled components in the requested linear O (V + E) time, then you're done. It may seem a little overkill, but it solves the problem. To find all strongly related components, assuming your graph is represented as an adjacency list, perhaps the simplest O (V + E) linear time algorithm is Kosaraju's code, see for example http://en.wikipedia.org/ wiki / Kosaraju% 27s_algorithm
Once you find all the strongly connected components, it is quite easy to check if there is a pair of strongly connected components that are not connected in any way by considering a condensed graph where the nodes are strongly connected by components and there is an edge if there is an edge between any two nodes selected from the two connected components.
source to share
Here are some tips to help you get started:
-
Try to fix this problem first when the graph you provided is DAG. What should be the structure of the DAG for any pair of nodes to be at least loosely coupled?
-
If you are calculating the strongly connected components of a graph, these SCCs themselves form a DAG. Could you use this observation in conjunction with your algorithm for part (1) to form an algorithm that works on arbitrary graphs?
Hope this helps!
source to share
If you can find strongly connected components, then you, conversely, know the vertices that are also not connected.
Wiki: http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm is pretty instructive. I have implemented the algorithm and is available here. Executed in O (v + E). We assume that the graph is maintained as an adjacency list.
Link for Implementing Kosaraju in Java
Try it, I hope you won't find any errors :-)
source to share