如何在python中表示图形/树以及如何检测周期？

Question

我想在python中实现kruskal的算法如何才能表示树/图表以及我应该采用什么方法来检测周期？

Answer 1

表示它的最简单方式(在我看来)是使用数组列表的dict :

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()只是表示算法应该是什么样子的假人.