首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构图在python中的应用

数据结构图在python中的应用

作者头像
用户1634449
发布2018-06-29 12:19:54
1.1K0
发布2018-06-29 12:19:54
举报
文章被收录于专栏:Python专栏Python专栏

程序世界里,有很多的数据结构,比如:堆、栈、链表等等,今天要讲的就是图数据结构啦。

相信大家都使用过或者听说过图数据库吧,我们就来看看最简单的图数据结构算法。

首先先来看一下图长什么样

从上图能看出,比如节点A可以到达C、D、B,节点B只能到达E。

ok,这就是最基本的了,接下来来了解下游戏规则,我们需要列出所有可能的路径,比如:列出A到E的所有路径。

而在代码里,我们可能需要首先通过 字典+列表 的方式给出路径的设计,比如:

Graph = {'A': ['B', 'C', 'D'],
             'B': ['E'],
             'C': ['D', 'F'],
             'D': ['B', 'E', 'G'],
             'E': [],
             'F': ['D', 'G'],
             'G': ['E']}

在接下来,我们需要告诉程序,我们需要从哪里开始,走到哪里去,也就是常说的起始点和终点。

search_graph(Graph, 'A', 'E')

让我们来看下完整的代码吧:

def search_graph(graph: dict, start, end):
    _ret = []
    generate_path(graph, [start], end, _ret)
    # 这一步的排序可有可无,只不过为了显示好看
    _ret.sort(key=lambda x: len(x))
    return _ret


def generate_path(graph: dict, path, end, ret: list):
    _state = path[-1]
    # 如果起始点和终点是同一个位置,则结束
    if _state == end:
        ret.append(path)
    else:
        for _item in graph[_state]:
            if _item not in path:
                # path + [_item] 就是递归调用的关键参数,path的组成
                generate_path(graph, path + [_item], end, ret)


if __name__ == '__main__':
    _GRAPH = {'A': ['B', 'C', 'D'],
             'B': ['E'],
             'C': ['D', 'F'],
             'D': ['B', 'E', 'G'],
             'E': [],
             'F': ['D', 'G'],
             'G': ['E']}
    _ret = search_graph(_GRAPH, 'A', 'E')
    print("******************")
    print(' path A to E')
    print("******************")
    for i in _ret:
        print(i)

结果如下图:

主要的逻辑,大家可以拿张纸出来画画,有什么不懂的,也可以加群来聊。

好啦,今天的内容就到这了,感兴趣的你,可以试试能不能走出来~

所有的代码都已上传至我的github:https://github.com/MiracleYoung/exercises

如果你对今天的内容还感兴趣的话,何不点个赞再走呢?

如果感兴趣到想赞赏我,就不要犹豫啦~


本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-06-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 猿媛牧场 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
数据库
云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档