wu :: forums - Print Page


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

        riddles >> cs >> Path in a graph
        
(Message started by: bazinga on Sep 24^th, 2012, 9:25pm)

Title: Path in a graph
Post by bazinga on Sep 24^th, 2012, 9:25pm

Given a directed graph, give a linear time algorithm to find out whether there exist a directed path that touches each vertex exactly once.

[hideb]
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.)
[/hideb]

Title: Re: Path in a graph
Post by towr on Sep 25^th, 2012, 11:24pm

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.