Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find mother vertex in a directed graph in O(n+m)? [closed]

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices G can be reached by a directed path from v Give an O(n+m) algorithm to test whether graph G contains a mother vertex.

(c) from Skiena manual

Found only O(n(n+m)) way

like image 500
yetanothercoder Avatar asked Nov 30 '10 07:11

yetanothercoder


2 Answers

Algorithm::

a) Do DFS/BFS of the graph and keep track of the last finished vertex 'x' .

b) If there exist any mother vertex, then 'x' is one of them. Check if 'x' is a mother vertex by doing DFS/BFS from vertex 'x'.

Time Complexity O(n+m) + O(n+m) = O(n+m)

like image 115
Nishant Avatar answered Nov 07 '22 07:11

Nishant


step1. Do topological sorting of vertices of directed graph.

step2. Now check whether we can reach all vertices from first vertex of topologically sorted vertices in step 1.

To perform a step 2, again initialize array discovered[i] to false and do dfs startin from first node of topologically sorted vertices.

If all vertices can be reached, then graph has mother vertex, and mother vertex will be the former of topologically sorted vertices.

time complexity: step1 takes O(n + m), step 2 takes O(n + m) so total O(n+m) + O(n+m) = O(n+m)

like image 39
Rahul Biswas Avatar answered Nov 07 '22 05:11

Rahul Biswas