Python无向图邻接矩阵实现
一、无向图邻接矩阵表示
Python使用邻接矩阵实现无向图，通过两个列表存储数据：一个列表存储顶点，一个二维列表存储边。
构造函数
邻接矩阵构造函数内含两个成员变量：
- 顶点:一维列表存储顶点，
self.verts = []- 边:二维列表构成一个N*N矩阵（N为顶点个数），相连的两个顶点在对应的行和列位置填充1，未相连填充0，
self.mats = []
def __init__(self, verts, edges):
# 顶点是一个列表
self.verts = []
# 边是一个二维列表，是根据顶点N×N的二维列表（数组）
self.mats = []
for v in verts:
self.add_vert(v)
for e in edges:
self.add_edge(e[0], e[1])
二、无向图增加顶点
增加顶点有三个操作步骤：
在顶点列表中新增一个元素：
self.verts.append(val)在边列表中新增一行：
self.mats.append(row)在边列表中新增一列，即为每一行新增一个元素，通过while循环遍历列表中的每一行，然后在行中增加一列（包含上一步中新增的一行）：```
for row in self.mats: row.append(0)
# 添加顶点
def add_vert(self, val):
#
n = self.size()
# 顶点列表添加新元素
self.verts.append(val)
row = [0] * n
# 边列表添加一行
self.mats.append(row)
# 边列表添加一列（每一行增加一个元素）
for row in self.mats:
row.append(0)
三、无向图删除顶点
删除顶点与增加顶点步骤相同，唯一不同点是增加顶点是在顶点列表的尾部添加（append），而删除顶点则是可能删除任意顶点，因此pop需要指定下标，同样三个步骤：
顶点列表中删除（pop）一个顶点元素：
self.verts.pop(i)边列表中删除指定顶点所在的行：
self.mats.pop(i)边列表中删除一列，即为每一行删除一个元素，通过while循环遍历边列表的每一行，然后在行中删除指定的下标元素：```
for row in self.mats: row.pop(i)
# 删除顶点,根据顶点的索引删除
def remove_vert(self, i):
if self.size() == 0:
raise IndexError("矩阵为空")
# 顶点列表移除指定索引顶点
self.verts.pop(i)
# 边列表移除指定索引顶点行
self.mats.pop(i)
# 按行遍历边列表，逐行删除指定索引所在的列
for row in self.mats:
row.pop(i)
四、无向图边操作
无向图中的边操作：新增和删除相对比较简单。唯一需要注意的是，边连接的是两个顶点，而邻接矩阵是对角线对称的，因此需要操作两次，即对顶点的行和列均需要进行操作。
注意：增加、删除边时，不能为同一个顶点增加边
if r < 0 or c < 0 or r >= self.size() or c >= self.size() or r == c:
# c:行索引，r：列索引
def add_edge(self, r, c):
if r < 0 or c < 0 or r >= self.size() or c >= self.size() or r == c:
raise IndexError('越界')
self.mats[r][c] = 1
self.mats[c][r] = 1
def remove_edge(self, r, c):
if r < 0 or c < 0 or r >= self.size() or c >= self.size() or r == c:
raise IndexError('越界')
self.mats[r][c] = 0
self.mats[c][r] = 0
五、全部代码
from prettytable import PrettyTable
class GraphMatrix:
def __init__(self, verts, edges):
# 顶点是一个列表
self.verts = []
# 边是一个二维列表，是根据顶点N×N的二维列表（数组）
self.mats = []
for v in verts:
self.add_vert(v)
for e in edges:
self.add_edge(e[0], e[1])
def size(self):
return len(self.verts)
# 添加顶点
def add_vert(self, val):
#
n = self.size()
# 顶点列表添加新元素
self.verts.append(val)
row = [0] * n
# 边列表添加一行
self.mats.append(row)
# 边列表添加一列（每一行增加一个元素）
for row in self.mats:
row.append(0)
# 删除顶点,根据顶点的索引删除
def remove_vert(self, i):
if self.size() == 0:
raise IndexError("矩阵为空")
# 顶点列表移除指定索引顶点
self.verts.pop(i)
# 边列表移除指定索引顶点行
self.mats.pop(i)
# 按行遍历边列表，逐行删除指定索引所在的列
for row in self.mats:
row.pop(i)
# c:行索引，r：列索引
def add_edge(self, r, c):
if r < 0 or c < 0 or r >= self.size() or c >= self.size() or r == c:
raise IndexError('越界')
self.mats[r][c] = 1
self.mats[c][r] = 1
def remove_edge(self, r, c):
if r < 0 or c < 0 or r >= self.size() or c >= self.size() or r == c:
raise IndexError('越界')
self.mats[r][c] = 0
self.mats[c][r] = 0
def show(self):
tb = PrettyTable(self.verts)
for c in self.mats:
tb.add_row(c)
print(tb)
if __name__ == "__main__":
verts = ['a', 'b', 'c', 'd', 'e']
edges = [[0, 1], [0, 3], [1, 2], [2, 3], [2, 4], [3, 4]]
matrix = GraphMatrix(verts, edges)
matrix.show()
matrix.add_vert('f')
matrix.add_edge(1, 5)
matrix.show()
matrix.remove_vert(4)
matrix.show()
matrix.remove_edge(0, 3)
matrix.show()