Visit all nodes exactly once in a directed graph

Question

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?

Bathulda

to answer your question: yes it is possible. And now what have you tried so far? – Teetotalism

I run a bfs and I keep a bitmask that says which nodes I have visited. – Bathulda

Can you explain how can we do this? – Bathulda

@Teetotalism Can you write your solution? – Bathulda

Sorry, stackoverflow.com is not a code-writing service. – Clippard

Sorry, I was trying to say that I want him to explain his solution. – Bathulda

Answer 1

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.

Magnific