CODEWITHSUNDEEP
algorithmdata-structuresgraphgraph-theory
Praveen
Praveen

Reputation: 393

Directed Graph walk - visit every node at least once

I’m familiar with the Hamilton path for a directed graph - visit every node exactly once.

I’m looking for an algorithm to walk the graph so that I visit every node at least once. I can’t find the standard name for this problem, if any.

This graph is walkable - root-a-d-b-c Traversable graph

This graph is not walkable - because in my walk, if I reach c, I have no directed edge to reach a & d and conversely, if I walk to a, d; there’s no directed edge that takes me to b & c enter image description here

Hope that clarifies the question? Is there a standard name for this type of graph walk and an algorithm to solve it?

Upvotes: 2

Views: 724

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65468

Theorem: a directed graph is walkable if and only if its strongly connected components are totally ordered by reachability.

Proof sketch: (walkable implies condition) The existence of a walk implies that, for each two strongly connected components, a vertex from one or the other appears first in the walk. That component can reach the other. (condition implies walkable) Since there is full connectivity inside a strongly connected component, each is walkable on its own. We just have to concatenate the walks according to the total order, adding the necessary transitions.

The proof is constructive, so we can extract an algorithm.

Algorithm

  • Compute the strongly connected components.
  • Concatenate the strongly connected components in topological order. Actually Tarjan's algorithm will list them in reverse topological order, so this doesn't need to be a separate step.
  • For each adjacent pair in the previous list, use breadth-first search to find a shortest path.

In general, this algorithm does not find the shortest walk (that's NP-hard by reduction from Hamiltonian path).

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59204

I don't know if there's a name for a directed "walkable" graph, but it's not too hard to determine of a graph is walkable or not:

  1. Find all the strongly connected components using Tarjan's algorithn, for example
  2. Make a new directed graph of the connections between SCCs. This will be a DAG, and your original graph is walkable if and only if this DAG is walkable.
  3. To determine whether or not a DAG is walkable, do a topological sort. Then check that each vertex has an edge to the next.

Each of these steps takes linear time, so you get O(|V|+|E|) complexity for the whole algorithm.

Upvotes: 3

Related Questions