数据结构图在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

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

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


原文发布于微信公众号 - 猿媛牧场(xpchuiit)

原文发表时间:2018-06-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

聊聊一些垃圾回收算法

不是所有的GC都是完美的,每一个GC算法的选用都有其背后的原因。而我们选择GC算法,有四个评价标准:吞吐量(也就是说,在单位时间内你回收的对象(这里是指通过应用...

682
来自专栏java一日一条

编写难于测试的代码的5种方式

有一次,我在一个讲座上听到主持人问听众如何故意编写难于测试的代码。在场的小伙伴都惊呆了,因为没有任何人会故意写这种糟糕的代码。我记得他们甚至给不出一个好的答案。

922
来自专栏OY写东西的地方

使用Typescript给JavaScript做静态类型检查

笔者所说的这个项目,是一个运行了接近五年的老项目,代码横跨es3到es6。而且代码风格由于项目的人员流动也各异。由于项目人数越来越多,以前留下的技术债造成的危害...

860
来自专栏Golang语言社区

Go语言的 10 个实用技术--转

十条有用的 Go 技术   这里是我过去几年中编写的大量 Go 代码的经验总结而来的自己的最佳实践。我相信它们具有弹性的。这里的弹性是指:   某个应用需要适配...

3417
来自专栏阿凯的Excel

Python读书笔记14(字典的增改删)

上期分享了字典的创建于访问,本期和大家分享的是最重要的营改增政策! 不好意思!串台了,本期和大家分享的是字典的增改删! 一、我们先创建一下新的字典 ? 二、添加...

2738
来自专栏北京马哥教育

shell十三问,为linux学习打基础(二)

本文整理并转自CU上的帖子[学习共享] shell 十三問?,此贴是2003年发表的,但却是相当不错的linux基础知识汇集贴,原帖主使用的台湾风格,本文加以简...

3554
来自专栏jeremy的技术点滴

golang语言常见范式

3234
来自专栏做全栈攻城狮

C#入门教程(二)–C#常用快捷键、变量、类型转换-打造C#

C#入门教程(一)–.Net平台技术介绍、C#语言及开发工具介绍-打造C#学习教程

1055
来自专栏菜鸟前端工程师

JavaScript学习笔记025-闭包0缓存计算0console属性

903
来自专栏王亚昌的专栏

实战设计模式系列-Strategy(策略)

    项目最近需要写一个逻辑srv,srv的业务逻辑比较简单,收包、解包、根据命令字进行业务处理、回包。 考虑每一次请求都是一项任务,而逻辑srv是一个任务管...

861

扫码关注云+社区