在图实现中查找所有循环

Question

我已经找到了一个简单的算法来查找图中的所有循环，可以在这里找到。我还需要打印出循环，这个算法能实现吗？请查看下面的代码。

我已正确地得到了循环的数量！

node1、node2是整数。visited是一个字典。

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)

- Kalyan Chavali

Answer 1

当然可以构建路径，现在您可以使用递归来完成，但我并不喜欢在类中管理临时状态。

这里是一个使用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 不能返回到自身。

- AChampion

---

我尝试了 graph = {2: [4, 1], 3: [2], 1: [4, 3]}，但总是出现 KeyError: 4。 - nosense

你的图表没有描述完整的图表（即它缺少节点4的定义）。你可以在图表定义中添加4: []，或者将for next_state in graph[state]:替换为for next_state in graph.get(state, []):。 - AChampion

谢谢您的解释。我通过判断一个数字是否在字典键中来解决了这个问题。但是我发现，当处理最多有1000个顶点的图形时，这种方法运行非常缓慢（http://rosalind.info/problems/cte/）。您知道任何更快的算法吗？我还尝试了networkx内置的simple_cycles函数，但仍然很慢。 - nosense

当你只需要通过给定的边找到一个循环时，找到所有循环是过度的。给定的边严重减少了搜索空间。从边的末尾开始，到达边的开头，例如通过边(2, 3) max(len(p)+1 for p in dfs(graph, 3, 2))。 - AChampion

我该如何调用函数，以便只获取从特定的节点开始的循环？ - Shahriar

Answer 2

可以的。 你只需要存储每个顶点的父节点，然后在父节点数组上迭代（直到找到起始顶点）以在找到环时打印出来。

- kraskevich

---

我这里没有为顶点做父子关系。它们只是整数。所有的边都以元组形式存储在EList中。这样是否仍然可行？ - Kalyan Chavali

哦，我有每个顶点的邻接表。我该如何使用它来打印？ - Kalyan Chavali

@KalyanChavali 你可以创建一个额外的数组（列表，映射）parent，并在dfs中通过边从v到u时将parent[u] = v赋值。 - kraskevich

我尝试了这种方法，但它会陷入无限循环。请在此处找到代码[链接]https://github.com/kalyan-ch/graphs/graph.py - Kalyan Chavali