patternMinor
Visit all vertices on directed graph
Viewed 0 times
visitgraphalldirectedvertices
Problem
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.
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.
Solution
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.)
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.)
Context
StackExchange Computer Science Q#24657, answer score: 2
Revisions (0)
No revisions yet.