1

I'm currently working on a project in my spare time where I need to check for the existence of a Hamiltonian path within a graph, however, it doesn't matter where the path begins or ends, only that one exists within the graph.

I copied this code from another user on here:

def hamilton(graph, start_v):
  size = len(graph)
  to_visit = [None, start_v]
  path = []
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      for x in set(graph[v])-set(path):
        to_visit.append(None)
        to_visit.append(x)
    else:
      path.pop()
  return path

There is obviously a parameter for the starting value. Now my first instinct would be to just iterate the function and run it for every starting vertex, but since I'm going to be running this on graphs with 100+ vertices it would take ages to run to completion. I don't really need to know what the path through all of the vertices is, I just need to know that one exists if that helps.

How would I adapt this to give an arbitrary starting location?

Matthaeus Catuvellauniensis
  • 13
  • 2
  • Maybe this is your answer: https://stackoverflow.com/questions/1987183/randomized-algorithm-for-finding-hamiltonian-path-in-a-directed-graph – duffymo Jan 26 '21 at 12:00

1 Answers1

0

You could insert a new "start" vertex into the graph, with edges to every other vertex, then search for a Hamiltonian path starting at this "start" vertex. If a path is found, then one exists in the original graph simply by deleting the "start" vertex from the beginning of the path; conversely, if there is a Hamiltonian path in the original graph starting from any vertex, then there will be one in the new graph starting at the "start" vertex.

That said, this won't actually be more efficient than just calling the existing algorithm once for each starting vertex, because the algorithm you have works by brute force anyway.

kaya3
  • 47,440
  • 4
  • 68
  • 97