Implementation
class HamiltonianPath:
def __init__(self, edges):
self.g = HamiltonianPath.__create_graph(edges)
@ staticmethod
def __create_graph(edges):
g = {}
for u, v in edges:
g[u] = set()
g[v] = set()
for u, v in edges:
g[u].add(v)
return g
def getHamiltonianPath(self):
def dfs(start):
s = [(start, None)]
h_path = []
visited = set()
while s:
top, parent = s.pop()
h_path.append(top)
visited.add(top)
if len(h_path) == len(self.g):
return h_path
none = True
for edge in self.g[top]:
if edge not in visited:
none = False
s.append((edge, top))
if none:
if not s:
return []
# back track until we reach the next element in the stack
# backtracking in this context means iterating backwards
# through the current path we collected
#
# our stopping condition is when:
# 1. The current element in the path is connected to the top of the stack
# 2. The parent of the top of the stack is current path element
while h_path and s[-1][0] not in self.g[h_path[-1]] or s[-1][1] != h_path[-1]:
tmp = h_path.pop()
visited.remove(tmp)
return []
for vertex, _ in self.g.items():
s = dfs(vertex)
if s:
return s
return []
At this point in time, the stack has elements [8,3]. Once the algorithm discovers that path 1...9 is not a Hamiltonian path, it must backtrack to find the top element in the stack [3]. However we can see that vertex 13 is connected to vertex 3. We need another piece of information, which is that [3] has come from parent [1]. So we backtrack until our path contains this parent element as well.
Last updated