Python 数据结构-图

Python 算法基础之图结构表示方法总结。

  图是一种重要的数据结构,它可以代表各种结构和系统,从运输网络到通信网络,从细胞核中的蛋白质相互作用到人类在线交互。

  图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图 G 中的顶点的集合,E是图 G 中边的集合。如下图:

  下面将以如图所示的有向图为例进行说明 Python 中图结构的表示方法。

邻接集合

  对于图结构的实现来说,最直观的方式之一就是使用邻接列表。基本上就是针对每个节点设置一个邻接列表,可以使用集合、列表或者字典来实现。第一种是针对每个节点设置一个邻居集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 将节点的编号赋值给相应的节点,方便操作
a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f}, # a
{c, e}, # b
{d}, # c
{e}, # d
{f}, # e
{c, g, h}, # f
{f, h}, # g
{f, g} # h
]
# 列表中每个集合是每个节点邻接点集

  N(v) 代表 v 的邻接点集。测试:

1
2
3
4
>>> b in N[a] # 节点 b 是否是 a 的邻居节点
True
>>> len(N[a]) # 节点 a 的出度
5

邻接列表

  与邻接集合类似,只是针对每个节点设置的是一个包含所有邻居的列表,而不是集合。

1
2
3
4
5
6
7
8
9
10
11
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]
]

加权邻接字典

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

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

  测试:

1
2
3
4
5
6
>>> b in N[a] # b 是否是 a 的邻居节点
True
>>> len(N[f]) # 度
3
>>> N[a][b] # 边(a, b)的权重
2

邻接集字典

  以上图的表示方法都使用了list类型,其实,也可以使用嵌套的字典结构来实现。

1
2
3
4
5
6
7
8
9
10
N = {'a':set('bcdef'),
'b':set('ce'),
'c':set('d'),
'd':set('e'),
'e':set('f'),
'f':set('cgh'),
'g':set('fh'),
'h':set('fg')
}
# 如果省略set()构造器,用邻接字符串表示键值,工作方式相当于邻接列表

  当然,字典的值也可以使用列表来表示。测试:

1
2
3
4
>>>'h' in N['a'] # a 是否有到 h 的边
False
>>>len(N['g']) # 节点 g 的度
2

嵌套字典

  也可以使用嵌套字典的方式来实现加权图。

1
2
3
4
5
6
7
8
9
N = {'a':{'b':2, 'c':1, 'd':3, 'e':9, 'f':4},
'b':{'c':4, 'e':3},
'c':{'d':8},
'd':{'e':7},
'e':{'f':5},
'f':{'c':2, 'g':2, 'h':2},
'g':{'f':1, 'h':6},
'h':{'f':9, 'g':8}
}

  测试:

1
2
3
4
5
6
>>>'f' in N['e'] # e 是否有到 f 的边
True
>>>len(N['e']) # 节点 e 的度
1
>>>N['a']['e'] # 边(a, e)的权重
9

邻接矩阵

  图的另一种常见表示法就是邻接矩阵。这种表示的主要不同之处在于,它不再列出每个节点的所有邻居节点,而是会将每个节点可能的邻居位置排成一行(也就是一个数组,用于对应图中每一个节点),然后用某种值(如True或False)来表示相关节点是否为当前节点的邻居。

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

  测试:

1
2
3
4
>>> N[a][b] # a 是否有到 f 的边
1
>>> sum(N[f]) # 节点 f 的度,不能再用 len 函数
3

  注意,邻接矩阵中:

  • 主对角线为自己到自己,为 0
  • 行和为出度
  • 列和为入度

加权邻接矩阵

  对不存在的边赋予无限大权值的加权矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
a, b, c, d, e, f, g, h = range(8)
inf = float("inf") # 无穷大
W = [
[ 0, 2, 1, 3, 9, 4, inf, inf], # a
[inf, 0, 4, inf, 3, inf, inf, inf], # b
[inf, inf, 0, 8, inf, inf, inf, inf], # c
[inf, inf, inf, 0, 7, inf, inf, inf], # d
[inf, inf, inf, inf, 0, 5, inf, inf], # e
[inf, inf, 2, inf, inf, 0, 2, 2], # f
[inf, inf, inf, inf, inf, 1, 0, 6], # g
[inf, inf, inf, inf, inf, 9, 8, 0] # h
]

  测试:

1
2
3
4
5
6
>>> W[a][b] < inf # a 是否有到 b 的边
True
>>> W[c][e] < inf # c 是否有到 e 的边
False
>>> sum(1 for w in W[a] if w < inf) - 1 # 度
5

参考资料:

Hetland M L. Python Algorithms: mastering basic algorithms in the Python Language[M]. Apress, 2014.

坚持原创技术分享,您的支持将鼓励我继续创作!