查找图实现中的所有循环 [英] 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 是整数.访问的是一本字典

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)

推荐答案

是的，当然你可以构造路径，现在你可以递归地完成，但我不喜欢在类中管理临时状态.

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.

这是一个使用 stack 的简单实现:

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]]

注意:4 不能回到自身.

Note: 4 cannot get back to itself.

这篇关于查找图实现中的所有循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！