グラフのすべてのサイクルを見つける

Question

グラフ内のすべてのサイクルを見つける簡単なアルゴリズムを見つけましたhere。私もサイクルを印刷する必要があります、それはこのアルゴリズムで可能です。以下のコードを見つけてください。

サイクル数が正しく表示されています。

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

Answer 1

はい、可能です。 各頂点の親を保存してから、親の配列を反復して（開始頂点に達するまで）、サイクルを見つけたら印刷することができます。

Answer 2

もちろん、パスを構築することはできますが、再帰的に行うことはできますが、クラスの一時的な状態を管理するのは大したファンではありません。

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

注：

はここstackを使用した簡単な実装だ4は、それ自体に戻って取得することはできません。