在图形实现中查找所有的周期 [英] Find all cycles in a graph implementation

问题描述

我找到了一个简单的算法来查找图表此处中的所有循环。我也需要打印出这些循环，这个算法有可能吗？请找到下面的代码。

我得到正确的循环次数！

node1，node2是整数。访问是一本字典

  def dfs（self，node1，node2）：
 if self.visited [node2]： 
 if（node1 == node2）：
 self.count + = 1 
 print node2 
 return 
 
 self.visited [node2] = True 
 
 for self.adj_lst [node2-1]：
 self.dfs（node1，x）
 
 self.visited [node2] = False 
 
 def allCycles（self）：
 self.count = 0 
用于self.VList中的x：
 self.dfs（x.num，x.num）
 self.visited [x.num] = True 
 
 print循环次数：+ str（self.count）
  

解决方案

当然，您可以构建路径，现在您可以递归执行该操作，但我不是管理临时状态的好粉丝班上。

以下是使用 stack 的简单实现：

  def dfs（图形，开始，结束）：
 fringe = [（start，[]）] 
边缘：
 state，path = fringe .pop（）
如果路径和状态==结束：
产生路径
继续
在图形[state]中为next_state：
如果next_state在路径中：
 continue 
 fringe.append（（next_state，path + [next_state]））
 
>>> graph = {1：[2,3,5]，2：[1]，3：[1]，4：[2]，5：[2]} 
>>> cycles = [[node] + dfs中路径的图中节点的路径（图形，节点，节点）] 
>>> len（周期）
 7 
>>>周期
 [[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不能回到自己身上。

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)

解决方案

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.

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