Home
> Uncategorized > Find the node of a graph from which all nodes are reachable

## Find the node of a graph from which all nodes are reachable

If we have a graph G=(V,E) and all vertices are reachable from vertex s, then our problem is to find such a vertex s.

Solution: Solution to this problem is in DFS of the graph. Before going to the algorithm, we need to consider the following properties of DFS.

i) DFS tree produced by the DFS algorithm is always a tree ( it means that it must be acyclic, whatever the graph is)

Here is the algorithm that reports if a given graph has a vertex from which all other vertex are reachable.

DFS-Visit(u) time = time + 1; u.start_time = time; child= 0; Color = GRAY; for each v belongs to adj[u] { if ( v.color == WHITE ) { DFS-visit(v); child = (v.finish_time - v.start_time + 1 ) / 2; } } u.finish_time = time + 1; u.color = BLACK; u.child = child + 1; // child include number of nodes this node visits including itself. if ( u.child == |V| ) ## Report u as source vertex ##

In fact, this is the solution for the following problem

5-26. 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 a given vertex*v*is a mother of*G*, where*n*= |*V*| and*m*= |*E*| . - Give an
*O*(*n*+*m*) algorithm to test whether graph*G*contains a mother vertex.

Advertisements

Categories: Uncategorized

Hi! Would you mind if I share your blog with my zynga group? There’s a lot of people that I think would really enjoy your content. Please let me know. Cheers|