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

发布时间：2020-12-16 23:37:40 所属栏目：Python 来源：网络整理

导读：我想在 python中实现kruskal的算法,我该如何去表示树/图,以及我应该采用哪种方法来检测周期？解决方法表达它的最简单的方法(在我看来)是通过使用数组列表的dict： graph = {}graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)] 寻

我想在 python中实现kruskal的算法,我该如何去表示树/图,以及我应该采用哪种方法来检测周期？

解决方法

表达它的最简单的方法(在我看来)是通过使用数组列表的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()只是用于表示算法应该如何的模拟器.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!