CODEWITHSUNDEEP
c++pathdirected-graph
John Smith
John Smith

Reputation: 69

Visit all nodes exactly once in a directed graph

I have a directed graph and I want to find a path that visits every node exactly one time. I want to do this with a good complexity. Is this possible? And if yes, how?

Upvotes: 6

Views: 8954

Answers (1)

DaveFar
DaveFar

Reputation: 7457

You are searching for a Hamiltonian path, which is a simple open path that contains each node exactly once.

Finding a Hamiltonian path in a given graph is NP-complete. In fact, determining whether a given (directed or undirected) graph contains a Hamiltonian path is already NP-complete (proven via reduction from e.g. the vertex cover problem).

If you still want to code it, here is an implementation on github. If you want a fast solution, maybe a heuristic is sufficient (for instance inspired by DNA molecules, or a solution that works fast on a subset of graphs. For instance, if you have a DAG, you can do a topological sort and then check if successive vertices are connected. If so, the topological sort gives a Hamiltonian path.

Upvotes: 10

Related Questions