图是一种重要的数据结构,它可以代表各种结构和系统,从运输网络到通信网络,从细胞核中的蛋白质相互作用到人类在线交互。
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图 G 中的顶点的集合,E是图 G 中边的集合。如下图:
下面将以如图所示的有向图为例进行说明 Python 中图结构的表示方法。
邻接集合
对于图结构的实现来说,最直观的方式之一就是使用邻接列表。基本上就是针对每个节点设置一个邻接列表,可以使用集合、列表或者字典来实现。第一种是针对每个节点设置一个邻居集合。
|
|
N(v) 代表 v 的邻接点集。测试:
|
|
邻接列表
与邻接集合类似,只是针对每个节点设置的是一个包含所有邻居的列表,而不是集合。
|
|
加权邻接字典
使用字典类型来代替集合或列表来表示邻接表。在字典类型中,每个邻居节点都会有一个键和一个额外的值,用于表示与其邻居节点(或出边)之间的关联性,如边的权重。
|
|
测试:
|
|
邻接集字典
以上图的表示方法都使用了list类型,其实,也可以使用嵌套的字典结构来实现。
|
|
当然,字典的值也可以使用列表来表示。测试:
|
|
嵌套字典
也可以使用嵌套字典的方式来实现加权图。
|
|
测试:
|
|
邻接矩阵
图的另一种常见表示法就是邻接矩阵。这种表示的主要不同之处在于,它不再列出每个节点的所有邻居节点,而是会将每个节点可能的邻居位置排成一行(也就是一个数组,用于对应图中每一个节点),然后用某种值(如True或False)来表示相关节点是否为当前节点的邻居。
|
|
测试:
|
|
注意,邻接矩阵中:
- 主对角线为自己到自己,为 0
- 行和为出度
- 列和为入度
加权邻接矩阵
对不存在的边赋予无限大权值的加权矩阵。
|
|
测试:
|
|
参考资料:
Hetland M L. Python Algorithms: mastering basic algorithms in the Python Language[M]. Apress, 2014.