Find All Cycles In A Graph Implementation

I have found a simple algorithm to find all cycles in a graph here. I need to print out the cycles too, is it possible with this algorithm. Please find the code below. I'm getting

Solution 1:

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:

defdfs(graph, start, end):
    fringe = [(start, [])]
    while fringe:
        state, path = fringe.pop()
        if path and state == end:
            yield path
            continuefor 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.

Solution 2:

Yes, it's possible. You can just store the parent of each vertex and then iterate over the array of parents (until you reach the start vertex) to print the cycle when you find one.