查找有向图和无向图中的所有循环

在下面的代码，如果一个周期中的有向图的存在与否返回True或False：

：

def cycle_exists(G):      
    color = { u : "white" for u in G } 
    found_cycle = [False]    

    for u in G:       
     if color[u] == "white": 
      dfs_visit(G, u, color, found_cycle) 
     if found_cycle[0]: 
      break 
    return found_cycle[0] 


def dfs_visit(G, u, color, found_cycle): 
    if found_cycle[0]:       
     return 
    color[u] = "gray"       
    for v in G[u]:        
     if color[v] == "gray":     
      found_cycle[0] = True  
      return 
     if color[v] == "white":      
      dfs_visit(G, v, color, found_cycle) 
    color[u] = "black"

在下面的代码，如果一个周期中的无向图的存在与否返回True或False

def cycle_exists(G):         
    marked = { u : False for u in G }  
    found_cycle = [False]              

    for u in G:       
     if not marked[u]: 
      dfs_visit(G, u, found_cycle, u, marked)  
     if found_cycle[0]: 
      break 
    return found_cycle[0] 

def dfs_visit(G, u, found_cycle, pred_node, marked): 
    if found_cycle[0]:        
     return 
    marked[u] = True         
    for v in G[u]:          
     if marked[v] and v != pred_node:    
      found_cycle[0] = True      
      return 
     if not marked[v]:        
      dfs_visit(G, v, found_cycle, u, marked) 

graph_example = { 0 : [1], 
        1 : [0, 2, 3, 5], 
        2 : [1], 
        3 : [1, 4], 
        4 : [3, 5], 
        5 : [1, 4] }

如何使用这些查找定向和无向图中存在的所有循环？

来源

2016-10-17 Angad

如果我理解的很好，你的问题是使用一个独特的算法来处理有向图和无向图。

为什么不能使用该算法检查无向图上的有向循环？ 非有向图是有向图的特例。你可以考虑一个无向边是由一个向前和向后的边构成的。

但是，这不是非常有效。一般来说，你的问题的陈述将表明图表是否定向。

来源

2016-10-17 20:45:07

查找有向图和无向图中的所有循环

回答

相关问题