Pythonでグラフ/ツリーを表現する方法とサイクルを検出する方法は？

Question

私はpythonでkruskalのアルゴリズムを実装したいのですが、どのようにツリー/グラフを表現することができますか、サイクルを検出するためにはどのようなアプローチが必要ですか？

Answer 1

（私の意見では）それを表現する最も簡単な方法は、配列リストの辞書を使用することです：

graph = {} 
graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)] 

サイクルを見つける簡単な方法は、BFまたはDFの検索を使用することです：

def df(node): 
    if visited(node): 
     pass # found a cycle here, do something with it 
    visit(node) 
    [df(node_id) for node_id in graph[node]] 

免責事項：これは実際のスケッチです。 neighbors()、visited()およびvisit()は、アルゴリズムの外観を表すための単なるダミーです。

Answer 2

Python Graph APIは、開始するのに適しています。

たとえば、NetworkXには、最小スパニングツリーを検出するKruskalのアルゴリズム実装があります。

ホイールを再発明して自分でやりたければ、それも可能です。