python 数据结构之图的储存方式

参考链接：https://blog.csdn.net/u014281392/article/details/79120406

所描述的图的结构为：

下面介绍不同的储存方式，我想不必详细分别是每个名称都是那种数据来存储的，或是一种，或是两种的组合，这不是再通用的规定约束而来的结果，只是列举了一些灵活的组合而已。

1.邻接集合

邻接集合就是把顶点的邻接点放在一个集合中

# 将节点的编号赋值给相应的节点，方便操作

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'}]

列表中每个集合是每个节点邻接点集

在python2.7中，set([1,3])这样表示，set()表示空集合．

在python3之后的版中，set{1,3}表示集合，空集合仍用set()表示．

#查看ａ的邻接节点有哪些

N[a]

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

# 检查g是否为a的一个邻接节点

'g' in N[a]

False

# 节点a的度

len(N[a])

5

2.邻接列表

数据结构和邻接集合差不多，唯一的不同是用列表来储存

# 表示同一个图

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'] ]

# 邻接列表表示图结构，与邻接集合的操作相同

3.邻接字典

临界字典与前面两个的不同之处在于，其不仅采用字典来储存，字典是键值对，键值对中的value用来表示边的权值这一信息，能表示出与邻居节点之间的关联性

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

N = [{'b':2, 'c':1, 'd':3, 'e':9, 'f':4},

     {'c':4, 'e':3},

     {'d':8},

     {'e':7},

     {'f':5},

     {'c':2, 'g':2, 'h':2},

     {'f':1, 'h':6},

     {'f':9, 'g':8}]

#操作

'e' in N[a]

True

 边的权值

N[a]['c']

1

4.嵌套字典

不用添加序号了

# 以上三种图的表示，都是使用了list类型

# 下面使用嵌套的字典结构

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}}

　　其他的操作和别的结构相同

# a,e之间链接权值

N['a']['e']

４．邻接矩阵

# 邻接矩阵，通过一个二维数组，对应图中的每个节点，使用０，１来表示相关节点是否为当前节点的邻居

# 可以使用嵌套list实现

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]]

# 检查a, b是否为相邻节点,即检查N[a][b]是否为１

N[a][b] == 1

True

# c节点的度 sum(N[c])

扩展邻接矩阵，实现一个没有自循环，对边加权、无自循环状态，对角线元素全部为０、加权，用权值替换真值、将不存在的边设置一个去穷大的权值(float('inf'))，或None

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

inf = float('inf')

N = [[  0,   2,   1,   3,   9,   4, inf, inf],

     [inf,   0,   4, inf,   3, inf, inf, inf],

     [inf, inf,   0,   8, inf, inf, inf, inf],

     [inf, inf, inf,   0,   7, inf, inf, inf],

     [inf, inf, inf, inf,   0,   5, inf, inf],

     [inf, inf,   2, inf, inf,   0,   2,   2],

     [inf, inf, inf, inf, inf,   1,   0,   6],

     [inf, inf, inf, inf, inf,   9,   8,   0]]

# 检查a,b是否互为相邻节点,只要邻接权值不是无穷大

N[a][b] < inf

巴特西

python 数据结构之图的储存方式

1.邻接集合

2.邻接列表

3.邻接字典

４．邻接矩阵

最新文章

热门文章