Python数据结构与算法之图结构(Graph)实例分析

Python数据结构与算法之图结构(Graph)实例分析,第1张

概述本文实例讲述了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,f},{c,e},{d},{e},{f},h},{f,g}]

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

>>> b in N[a]         # neighborhood membershipTrue>>> len(N[f])         # out-degree:出度3

加权邻接字典

使用 dict 类型来代替 set 或 List 来表示邻接集。在 dict 类型中,每个邻居节点都会有一个键和一个额外的值,用于表示与其邻居节点(或出边)之间的关联性,如边的权重。

a,h = range(8)N = [  {b:2,c:1,d:3,e:9,f:4},{c:4,e:4},{d:8},{e:7},{f:5},{c:2,g:2,h:2},{f:1,h:6},{f:9,g:8}]

客户端调用:

>>> b in N[a]         # neighborhood membershipTrue>>> len(N[f])         # out-degree3>>> N[a][b]          # Edge weight for (a,b)2

邻接矩阵

邻接矩阵是图的另一种表示方法,这种表示方法的主要不同在于,它不再列出每个节点的所有邻居节点。

a,h = range(8)N =[  [0,1,0],[0,1],]

关于邻接矩阵:

(1)主对角线为自己到自己,为0
(2)行和为出度
(3)列和为入度

更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串 *** 作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录 *** 作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

总结

以上是内存溢出为你收集整理的Python数据结构与算法之图结构(Graph)实例分析全部内容,希望文章能够帮你解决Python数据结构与算法之图结构(Graph)实例分析所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1201647.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-04
下一篇 2022-06-04

发表评论

登录后才能评论

评论列表(0条)

保存