如何在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有一個克魯斯卡爾算法的實現來尋找最小生成樹。

如果你想重新發明輪子並自己動手，那也是可以的。