Menu
Given a directed graph, how can we determine whether or not there exists a vertex v, from which all other vertices are reachable. the algorithm should be as efficient as possible.
I know how to do it if we are checking for a given vertex; we could do dfs on the reverse graph. But for this question, it seems inefficient to do it for every vertex in the graph.
Is there a better way?
729
One straight forward solution is to do a BFS traversal for every node present in the set and then find all the reachable nodes.
A digraph is called a tournament for every two vertices, the di- graph contains exactly one directed edge. Let G be a digraph of the outdegree k for some integer k > 0 whose edges are labeled with symbols a1,a2,...,ak so that for every vertex x ∈ V (G), the labels on the edges leaving x are a1,a2,...,ak.
This can be done by first finding Strongly Connected Components (SCC), which can be done in O(|V|+|E|) . Then, build a new graph, G' , for the SCCs (each SCC is a node in the graph), where each node has value which is the sum of the nodes in that SCC.
The length of the path is the number of edges, k. We say that w is reachablereachableIn graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex (and is reachable from ) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with and ends with .https://en.wikipedia.org › wiki › ReachabilityReachability - Wikipedia from u if there is a path from u to w. Note that every vertex is reachable from itself by a path that uses zero edges.
Use Kosaraju's algorithm to find the strongly connected components of the graph in time O(|V|+|E|). If you then "shrink" each component to a single node, you'll be left with a directed acyclic graph. There exists a vertex from which all others can be reached if and only if there is exactly one vertex in the DAG with in-degree 0. This is the vertex you're looking for - the so-called "mother vertex".
Note: This answer originally recommended using Tarjan's algorithm. Tarjan's is likely to be a bit faster, but it's also a bit more complex than Kosaraju's.
53
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
