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

前端之家收集整理的这篇文章主要介绍了如何在python中表示图形/树,以及如何检测周期?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我想在 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()只是用于表示算法应该如何的模拟器.

猜你在找的Python相关文章