Author |
Topic: Graph:Finding vertex that is all connected. (Read 3003 times) |
|
bazinga
Junior Member
 

Gender: 
Posts: 53
|
 |
Graph:Finding vertex that is all connected.
« on: Feb 19th, 2012, 3:27pm » |
Quote Modify
|
Given a directed graph G, give an algorithm to find a vertex 's'(if exists) from which all other nodes are reachable. hidden: | 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. |
|
« Last Edit: Feb 21st, 2012, 5:12pm by bazinga » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
    

Gender: 
Posts: 7527
|
 |
Re: Graph:Finding vertex that is all connected.
« Reply #1 on: Feb 20th, 2012, 5:23am » |
Quote Modify
|
Just compute the intersection of all neighbors of all nodes. PS: consider each node as its own neighbor.
|
« Last Edit: Feb 20th, 2012, 5:25am by Grimbal » |
IP Logged |
|
|
|
bazinga
Junior Member
 

Gender: 
Posts: 53
|
 |
Re: Graph:Finding vertex that is all connected.
« Reply #2 on: Feb 21st, 2012, 5:36pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
    

Gender: 
Posts: 7527
|
 |
Re: Graph:Finding vertex that is all connected.
« Reply #3 on: Feb 22nd, 2012, 1:00am » |
Quote Modify
|
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.
|
« Last Edit: Feb 22nd, 2012, 1:16am by Grimbal » |
IP Logged |
|
|
|
|