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 the number of cycles correctly!

node1, node2 are integers. visited is a dictionary

def dfs(self,node1, node2):
    if self.visited[node2]:
        if(node1 == node2):
            self.count += 1
            print node2
        return

    self.visited[node2] = True

    for x in self.adj_lst[node2-1]:
        self.dfs(node1, x)

    self.visited[node2] = False

def allCycles(self):
    self.count = 0
    for x in self.VList:
        self.dfs(x.num, x.num)
        self.visited[x.num] = True

    print "Number of cycles: "+str(self.count)

回答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:

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.

回答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.