数据结构图在python中的应用

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构图在python中的应用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1893字，纯文字阅读大概需要3分钟。

内容图文

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

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

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

从上图能看出，比如节点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

内容总结

以上是互联网集市为您收集整理的数据结构图在python中的应用全部内容，希望文章能够帮你解决数据结构图在python中的应用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端