algorithm - Finding a path through a connected component where every vertex is visited exactly once -

i have large graph of connected vertices (a connected component) , looking path goes through of them, never goes through 1 vertex twice. isn't possible. instance, in following example from wikipedia, obvious there no path visits every vertex no vertex visited more once:

but if tweaked slightly, has more edges (connections), there paths can go through every vertex once. i've tweaked , numbered vertices give 1 such path:

my graph one, know there possible path. however, quite large (20,000 vertices, each anywhere between 2 , 11 edges). implemented depth-first search , breadth-first search graph big find path through (it take long compute).

---

so question is: there algorithm can solve problem, more efficiently depth-first or breadth-first search?

it little bit traveling salesman problem except cities reachable specific other cities, , distance between equal.

the problem you're describing called hamiltonian path problem (a hamiltonian path 1 goes through every node once , once). problem is, unfortunately, known np-hard, there no known polynomial-time algorithms solving problem. result, unlikely find solution works efficiently using simple breadth-first search or depth-first search.

there famous dynamic programming algorithm solving problem. if search online "hamiltonian path dp," should find links on subject.