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.

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