Найти все циклы в направленном и неориентированном графике

Question

Я хочу, чтобы найти все циклы в направленном и ненаправленном графике.

Код ниже возвращает истину или ложь, если цикл существует или нет в ориентированном графе:

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" 

Код ниже возвращает истину или ложь, если цикл существует или нет в неориентированном графе:

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

Как использовать их для поиска всех циклов, которые существуют в направленном и неориентированном графе?

Answer 1

Если я хорошо понимаю, ваша проблема заключается в использовании одного уникального алгоритма для направленного и неориентированного графика.

Почему вы не можете использовать алгоритм для проверки направленных циклов на неориентированном графике? Нецелевые графы - частный случай ориентированных графов. Вы можете просто считать, что неориентированный край сделан из одного направленного вперед и назад.

Но это не очень эффективно. Как правило, в заявлении о вашей проблеме указывается, направлен или нет график.