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.

  1. Give an O(n + m) algorithm to test whether a given vertex v is a mother of G, where n = | V | and m = | E | .
  2. Give an O(n + m) algorithm to test whether graph G contains a mother vertex.
Advertisements
Categories: Uncategorized
  1. August 5, 2013 at 11:48 pm

    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|

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: