Visit all vertices on directed graph

Question

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.

Answer 1

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.

Answer 2

The first question you need to ask yourself, is when does it happen that there is no such vertex. For undirected graphs the answer is easy: such a vertex exists if and only if the graph is connected. DFS/BFS allow us to decompose the graph into connected components, and in particular we can find out whether there is more than one.

For directed graphs, it could happen that the underlying undirected graph is connected, yet the directed graph itself has no vertex from which you can reach all others. An example is a path with two edges directed toward the center. The corresponding refinement of the concept of connected components is strongly connected components, in which each vertex is reachable from any other. We can contract each strongly connected component to a single vertex, and then what we are left with is a DAG (directed acyclic graph; can you see why?). The question you should be asking yourself now is:

Given a DAG, when is there a vertex from which all other vertices are reachable?

Once you answer this question, all you need is an algorithm for finding strongly connected components. There are several DFS-based algorithms for that available on the web.

(Note: while this may not be the simplest solution, that is, there might be "shortcuts", the concept of strongly connected components is inherently useful and good to be aware of.)

Answer 3

Actually, your question is related to Eulerian graph. I think all you need to do is calculate the in-degrees and out-degrees of each vertex. If there is any vertex whose number of in-degrees is not equal to number of out-degrees, then the answer to your question is NO. if all vertices satisfy this property(inDegree[u] = outDegree[u]), then the answer is YES.

This is much easier than using DFS when you don't actually need to compute the cycle and only find if it exists.