如何在Python中表示图/树并检测循环？

Question

我想在Python中实现克鲁斯克尔算法，我该如何表示树或图呢？我应该采用什么方法来检测循环呢？

Answer 1

Python图形API是一个很好的入门地方。

比如说，NetworkX这个库里有一个克鲁斯克尔算法的实现，可以用来找到最小生成树。

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

Answer 2

我认为最简单的表示方法是用一个字典来存放 数组 列表：

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() 只是用来表示算法应该是什么样子的。