2
$\begingroup$

I am trying to find all mother vertex in a directed graph.

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

My Approach:

Do DFS on each vertex and check if all the vertex are reached on each start node. Time complexity : O(V*(V+E)).

I am looking for any better solutions with better complexity.

Any help would be appreciated.

$\endgroup$
5
$\begingroup$

Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.

$\endgroup$
  • $\begingroup$ Thanks. What do you mean by source in a component? If we take this graph,geeksforgeeks.org/wp-content/uploads/SCC.png It has 3 components,but has one mother vertex. $\endgroup$ – starkk92 Dec 4 '17 at 18:31
  • $\begingroup$ Actually 0,1,2 are all mother vertices. A source is a vertex with no incoming edges. $\endgroup$ – Yuval Filmus Dec 4 '17 at 18:53
  • $\begingroup$ Is there a way where I can find source vertices by SCC? $\endgroup$ – starkk92 Dec 4 '17 at 23:08
  • 1
    $\begingroup$ I'll let you figure that out. $\endgroup$ – Yuval Filmus Dec 4 '17 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.