Visit all vertices on directed graph

Problem Detail: 

We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. You can revisit vertices, but can't "use" edges twice or more time. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.

Asked By : Wanderer

Answered By : Roi Divon

Actually, you can use DFS to solve this problem.

Let's denote the set of all roots in graph $G$ as $R_G$

Lemma: for every run of DFS, the last DFS tree contains $R_G$. Let $ T_1, T_2, ..., T_t $ be the DFS trees found in a DFS run, such that $T_i$ is the ith tree that was discovered. Assume that there is a root $r$ such that $r \in T_i$ for $i<t$. Denote $r_k$ the root of the kth tree.

Since $r$ is a root, there is a route from $r$ to $r_t$ in $G$. let $u$ be the first vertex on that route such that $u \in T_t$, and let $w$ be the vertex before $u$ on that route.

When DFS discovers $w$, the vertex $u$ hasn't been discovered yet (since $u \in T_t$ and $w \in T_i$). So $w$ is a predecessor of $u$ in the DFS "forest" - and that contradicts that $u$ and $w$ are in different DFS trees.

We now conclude that $R_G \subseteq T_t$

So an algorithm to decide whether there is a root for $G$: we run a DFS, and then start a second DFS from the root of the last tree. if in that DFS run we've found all the vertices, and we have a root. otherwise, by the lemma, there is no root for $G$

The time complexity is ofcourse $O(|V| + |E|)$ since we did 2 runs of DFS.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24657