数据结构图在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算法,有四个评价标准:吞吐量(也就是说,在单位时间内你回收的对象(这里是指通过应用...

712
来自专栏落影的专栏

iOS开发笔记(一)

前言 iOS开发笔记(一) iOS开发笔记(二) iOS开发笔记(三) iOS开发笔记(四) 《开发笔记》系列记录一些开发中遇到的问题以及思考。 本文主...

3217
来自专栏前端侠2.0

如何用typescript 来写一个jquery 插件的 d.ts

1、Jquery 方法  。比如$.ajax( )    $.trim( )   它们特点就是直接绑在jquery 自身上。

3672
来自专栏王亚昌的专栏

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

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

901
来自专栏牛客网

爱奇艺远程一面

960
来自专栏jeremy的技术点滴

golang语言常见范式

3674
来自专栏CSDN技术头条

提高代码可读性的10个技巧

以下为译文: 如果你的代码很容易阅读,这也会帮助你调试自己的程序,让工作变得更容易。 代码可读性是计算机编程领域的一个普遍课题,这也是作为开发人员首先要学习的...

1947
来自专栏工科狗和生物喵

【计算机本科补全计划】图的连通性check by 并查集Union Find

具体的想法来自一篇写的超好的博客,如果底子不是很好,建议看下面这篇,当然如果可以给我顺手点个赞就更好了!!

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

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

1013
来自专栏Pythonista

Python之路,Day1 - Python基础1

python的创始人为吉多·范罗苏姆(Guido van Rossum)。1989年的圣诞节期间,吉多·范罗苏姆为了在阿姆斯特丹打发时间,决心开发一个新的脚本解...

1525

扫码关注云+社区