無向グラフのPythonでループをチェックする

Question

新しい行が追加されたときにグラフにループがあるかどうかをチェックするPythonプログラムを開発しようとしています。

私は最初の最短の長さによって順序付けられたリスト内の別の行を格納していますし、行は、クラスのとおりです。

class Line(): 
def __init__(self,node1,node2,length): 
    self.node1 = node1 
    self.node2 = node2 
    self.length = int(length) 
    self.drawn = False 

そして、ノードがリストに格納されます。

nodes = ["A","B","C","D","E","F"] 

私プログラムはルートをリストとして格納して実行しています：

route = [class(Line),class(Line)...] 

私がしたいのは、それがサイクルを形成しないことが追加されました。

何かのように：私は、大きなクラスの内部でメソッドを使用する予定

def check_loop(new_line,graphs): 
    add new line to graph 
    if there is a loop in graphs: 
     return False 
    else: 
     return True 

（フォーマットはゴミがあるので、申し訳ありませんが、これは私の最初の記事の一つである）

Answer 1

するかどうかを確認するにはツリー内にサイクルが作成されるのは非常に簡単なので、ノードを選択し、そのノードからツリー全体を最初に検索するだけです。到達するまでに以前にノードを訪れたことがある場合は、そのノードに到達した代替パスがあるため、サイクルがあることを知っています。