Author |
Topic: Graph:Finding vertex that is all connected. (Read 2997 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print