Yes of course you can construct the path, now you can do it recursively but I'm not a great fan of managing temporary state in the class.
Here's a simple implementations using a stack
:
def dfs(graph, start, end):
fringe = [(start, [])]
while fringe:
state, path = fringe.pop()
if path and state == end:
yield path
continue
for next_state in graph[state]:
if next_state in path:
continue
fringe.append((next_state, path+[next_state]))
>>> graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
>>> cycles = [[node]+path for node in graph for path in dfs(graph, node, node)]
>>> len(cycles)
7
>>> cycles
[[1, 5, 2, 1], [1, 3, 1], [1, 2, 1], [2, 1, 5, 2], [2, 1, 2], [3, 1, 3], [5, 2, 1, 5]]
Note: 4 cannot get back to itself.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…