如何在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有一个克鲁斯卡尔算法的实现来寻找最小生成树。

如果你想重新发明轮子并自己动手，那也是可以的。