Find a vertex that all other vertices can be reached from in a digraph

Question

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?

Answer 1

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.

Answer 2

The solution can be found by taking the concept from Kosaraju's algorithm for Strongly Connected Components. The idea is based on the following fact:

If there exists a vertex (or vertices), from which all other vertices are reachable, then this vertex would have the maximum finish time in a DFS traversal. So, the solution would look like:

// Utility function to find mother vertex 
//(vertex from which all other vertices are reachable)

public void findMotherVertex() {
    int motherVertex=0;

    for (int i=0;i<G.V();i++) {  //G.V() would return the no. of vertices in the graph
        if (!marked[i]) {  //marked - boolean array storing visited vertices
            dfs(i);
            motherVertex=i;
        }
    }

    //Check for this vertex if all other vertices have been already visited
    //Otherwise no mother vertex exists

    for (int i=0;i<G.V();i++) {
        if (!marked[i])
            return false;
    }

    System.out.println("Desired vertex is : " + motherVertex);
}

The above algorithm takes O(V+E) time to solve the problem.

Answer 3

I just invented the following algorithm.

• Start with an arbitrary vertex and mark it as 'visited'.
• Go 'up' in the graph going to an arbitrary parent vertex and mark it as 'visited'.
• Keep track of visited vertices on a stack.
• If you reach a vertex with no parent vertices, check whether it is indeed the vertex from which all other vertices are reachable.
• When reaching a vertex V already visited:
  1. Don't add the visited vertex V to the stack. Mark the previous vertex as the 'end' of a strongly connected component.
  2. Go down the stack until you reach the already visited vertex V. Along the way you remove all 'end' and 'start' markings. If the last marking removed was a 'start' marking, mark V as 'start', otherwise don't mark.
  3. Start at the top of the stack again and go down until you find a vertex with an unvisited parent (and continue with the first step of the algorithm) or until you reach the vertex marked as 'start' and check whether it is indeed a mother vertex from which all others are reachable.

The idea is that, since any vertex should be reachable from the mother vertex, we can just take an arbitrary path upward, until we can't go higher.

This way we only check the strongly connected components which can reach the starting vertex. In the case where there are a lot of strongly connected components with in-degree 0, this would be a clear advantage over Andy's algorithm.

Answer 4

import java.util.*;

public class FindMotherVertex {
    public static void main(String[] arg) {
        List<Edges> edges = Arrays.asList(
            new Edges(0, 1), new Edges(0, 2),
            new Edges(1, 3),
            new Edges(4, 1),
            new Edges(5, 2), new Edges(5, 6),
            new Edges(6, 4),
            new Edges(6, 0)
        );
        findMotherVertex(graph);

    }
    public static void findMotherVertex(Graph graph) {
        int motherVertex =  0;
        boolean[] visited = new boolean[7];

        for (int i=0;i<7;i++) {  
            if (visited[i] == false) {  //marked - boolean array storing visited vertices
                DFS(graph,i,visited);
                motherVertex= i;
            }

        }

        //Check for this vertex if all other vertices have been already visited
        //Otherwise no mother vertex exists

        for (int i=0;i<6;i++) {
            if (!visited[i]){ visited[i] = false;}

        }

        System.out.println("Mother vertex is : " + motherVertex);
    }

    public static void DFS(Graph graph, int v,boolean[] visited) {

        //create a stack used to do DFS
        Stack<Integer> stack = new Stack<>();
        stack.add(v);
        //Run While queue is empty

        while (!stack.isEmpty()) {
            //Pop vertex from stack
            v = stack.pop();

            if (visited[v])
                continue;
            visited[v] = true;
            System.out.print("(" + v + ")" + "===>");
// do for every edge
            List<Integer> list = graph.adj.get(v);
            for (int i = list.size() - 1; i >= 0; i--) {
                int u = list.get(i);
                if (!visited[u]) ;
                stack.push(u);
            }
        }

    }


    static class Graph {

        //List of List to represent Adajacency List
        List<List<Integer>> adj = new ArrayList<>();
        //Constructor to construct Graph

        public Graph(List<Edges> edges) {
            //Allocate memory for adjacency List
            for (int i = 0; i < edges.size(); i++) {
                adj.add(i, new ArrayList<>());
            }

            //Add edges to the undirected Graph
            for (Edges curr : edges) {
                adj.get(curr.src).add(curr.desc);


            }

        }

    }
}