Python数据结构与算法之图结构（Graph）实例分析_pythongraph资源-CSDN文库

版权申诉

数据结构与算法

163 浏览量 2020-09-21 04:16:18 上传评论收藏 75KB PDF 举报

资源推荐

资源详情

资源评论

Python数据结构与算法之图结构（数据结构与算法之图结构（Graph）实例分析）实例分析

主要介绍了Python数据结构与算法之图结构（Graph）,结合实例形式分析了图结构的概念、原理、使用方法及

相关操作技巧,需要的朋友可以参考下

本文实例讲述了Python数据结构与算法之图结构（Graph）。分享给大家供大家参考，具体如下：

图结构（Graph）——算法学中最强大的框架之一。树结构只是图的一种特殊情况。

如果我们可将自己的工作诠释成一个图问题的话，那么该问题至少已经接近解决方案了。而我们我们的问题实例可以用树结构

（tree）来诠释，那么我们基本上已经拥有了一个真正有效的解决方案了。

邻接表及加权邻接字典邻接表及加权邻接字典

对于图结构的实现来说，最直观的方式之一就是使用邻接列表。基本上就是针对每个节点设置一个邻接列表。下面我们来实现

一个最简单的：假设我们现有 n 个节点，编号分别为 0, …, n-1.

节点当然可以是任何对象，可被赋予任何标签或名称。但使用 0, …, n-1 区间内的整数来实现的话，会简单许多。因为如果我

们能用数字来代表节点，我们索引起来显然要方便许多。

然后，每个邻接（邻居）列表都只是一个数字列表，我们可以将它们编入一个大小为 n 的主列表，并用节点编号对其进行索

引。由于这些列表内的节点的顺序是任意的，所以，实际上，我们是使用列表来实现邻接集（adjacency sets）。这里之所以

还是使用列表这个术语，主要是因为传统。幸运的是，Python 本身就提供独立的 set 类型。

我们以下图为例，说明图结构的各种表示方法图结构的各种表示方法（当我们在执行与图相关的工作时，需要反复遵从一个主题思想，即一个图的最

佳表示方法应该取决于我们要用它来做什么）：

a, b, c, d, e, f, g, h = range(8)

N = [

{b, c, d, e, f},

{c, e},

{d},

{e},

{f},

{c, g, h},

{f, h},

{f, g}

]

在图论中，N(v) 代表的是代表的是 v 的邻居节点集的邻居节点集；

>>> b in N[a] # neighborhood membership

True

>>> len(N[f]) # out-degree：出度

3

加权邻接字典加权邻接字典

使用 dict 类型来代替 set 或 list 来表示邻接集。在 dict 类型中，每个邻居节点都会有一个键和一个额外的值，用于表示与其邻

居节点（或出边）之间的关联性，如边的权重。

a, b, c, d, e, f, g, h = range(8)

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

版权申诉

weixin_38664989

粉丝: 4
资源: 906

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip