数据结构图在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 条评论
登录 后参与评论

相关文章

来自专栏葡萄城控件技术团队

Spread for Windows Forms快速入门(4)---常用的单元格类型(上)

单元格类型定义了在单元格中呈现的信息的类型,以及这种信息如何显示,用户如何与其进行交互。单元格类型可以被赋给单个的单元格,整行或者整列。 用户可以使用两种不同的...

2036
来自专栏CVer

糟了!Python3.7.0 来了

美国时间6月27日晚8点,Python 3.7.0 经过多轮测试,终于发布了正式版,增强了多处特性功能,同时 3.6 也更新到 3.6.6 稳定版本。

1374
来自专栏calmound

匈牙利算法

今天学习了下匈牙利算法,发现这个早在几个月前学过的知识已经忘记的一干二净了,记得当初学习的时候只是看书,看论文,现在要好好的总结下,防止以后再次忘记。 此次总结...

2767
来自专栏zhisheng

Java研发方向如何准备BAT技术面试答案(下)

本文是针对文章《 Java研发方向如何准备BAT技术面试(超级干货)》里面的算法、数据结构、Linux和操作系统问题的一些答案。如有错误,还请各位网友指正。多谢...

97734
来自专栏诸葛青云的专栏

3分钟读懂C语言函数:这些例子一看就懂!|一键删除账户教学

最近发现,有些小伙伴对C语言的函数有些难以理解,其实呢,C语言的函数很好理解,只不过部分人在学习的时候,没有找到好的例子来类比理解而已。这篇文章会教大家如何去理...

712
来自专栏flutter开发者

[Flutter Widget]Chip

在前面的文章中我们看了下Tooltip的用法,在文章的最后也给大家留了一个问题,自定义自己的Tooltip。

1092
来自专栏程序员的SOD蜜

TDD(测试驱动设计):通过大量测试寻找最优解决方案

 这两天,我一直在做“测试人员”,不过跟一般的测试人员不同的是,我是在写代码做测试,这些代码是我头脑中的某种设计理念的表示,我坚信,只有不断的“测试”我的这些...

2037
来自专栏CDA数据分析师

人生苦短,为什么我要用Python?

本教程的目的是让你相信两件事:首先,Python 是一种非常棒的编程语言;其次,如果你是一名科学家,Python 很可能值得你去学习。本教程并非想要说明 Pyt...

503
来自专栏视觉求索无尽也

Markdown:入门

在 Markdown 中,你只需要在文本前面加上 # 即可,同理、你还可以增加二级标题、三级标题、四级标题、五级标题和六级标题,总共六级,只需要增加 # 即可,...

811
来自专栏chafezhou

小说python的字符串反转

1006

扫码关注云+社区