Author |
Topic: Path in a graph (Read 1760 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Path in a graph
« on: Sep 24th, 2012, 9:25pm » |
 Quote  Modify
|
Given a directed graph, give a linear time algorithm to find out whether there exist a directed path that touches each vertex exactly once.
| hidden: |
Is this correct? Find out strongly connected components of G and replace each SCC by a single node than start from a universal source and do a traversal. If you don't encounter any node with outdegree more than one and cover all the vertex than there is such a path. (Assuming the answer is always yes in a SCC.)
|
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Path in a graph
« Reply #1 on: Sep 25th, 2012, 11:24pm » |
Quote Modify
|
Suppose you have vertices and edges A->B->C->D->A, E->A, C->F; A,B,C,D forms a SCC, And while you do have E->SCC->F, there isn't actually a path that goes through all vertices exactly once. So your algorithm doesn't work.
It's a shame the question isn't to go along every edge once, because that'd be real easy to determine.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print