wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Graph:Finding vertex  that is all connected.
        
(Message started by: bazinga on Feb 19^th, 2012, 3:27pm)

Title: Graph:Finding vertex that is all connected.
Post by bazinga on Feb 19^th, 2012, 3:27pm

Given a directed graph G, give an algorithm to find a vertex 's'(if exists) from which all other nodes are reachable.

[hideb]
Is this correct or is there a more efficient solution?
Find all the strongly connected components of the graph. Now create another graph by replacing each SCC
by a single vertex. Now do a dfs from the node which doesn't have an incoming edge. If all the vertices are reachable from this vertex then any vertex in the SCC represented by this vertex is the required vertex.
[/hideb]

Title: Re: Graph:Finding vertex that is all connected.
Post by Grimbal on Feb 20^th, 2012, 5:23am

Just compute the intersection of all neighbors of all nodes.
PS: consider each node as its own neighbor.

Title: Re: Graph:Finding vertex that is all connected.
Post by bazinga on Feb 21^st, 2012, 5:36pm

Hi Grimbal,
Does it mean something like this...
For a directed graph with vertices numbered from 0 to 3 and following edges:
0-->1
0-->2
2-->3
3-->1
All the nodes are reachable from node 0.
While the neighbors are
0 --> {0,1,2}
1 --> {1}
2 --> {2,3}
3 --> {1,3}
If we do the intersection of all the neighbors it produces an empty set.

Title: Re: Graph:Finding vertex that is all connected.
Post by Grimbal on Feb 22^nd, 2012, 1:00am

Uh... I think I haven't read the problem carefully. I thought you were looking for a node that is connected to all other nodes. This is of course much easier.

Your solution looks correct.

You could also
1. Choose a node X and find the set of its descendants.
2. Choose a node Y that is not a descendant of X, find the descendants of Y.
3. If X is not a descendent of Y, there is no single origin.
4. If X is a descendent of Y, replace X by Y and restart at 2.