邻接矩阵是一种表示图的数据结构,其中矩阵的行和列代表图中的顶点,矩阵中的元素表示顶点之间的连接关系。如果顶点 i 和顶点 j 之间有边,则矩阵中第 i 行第 j 列的元素为 1(或边的权重),否则为 0。
以下是一个使用 Python 列表迭代邻接矩阵的示例:
# 定义一个无向图的邻接矩阵
adj_matrix = [
[0, 1, 1, 0],
[1, 0, 1, 0],
[1, 1, 0, 1],
[0, 0, 1, 0]
]
# 获取图的顶点数
num_vertices = len(adj_matrix)
# 迭代邻接矩阵
for i in range(num_vertices):
for j in range(i, num_vertices): # 只需迭代到 i,避免重复
if adj_matrix[i][j] == 1:
print(f"顶点 {i} 和顶点 {j} 之间有边")
原因:邻接矩阵需要存储所有顶点之间的连接关系,对于稀疏图来说,空间浪费较大。
解决方法:
# 定义一个无向图的邻接表
adj_list = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
# 迭代邻接表
for vertex, neighbors in adj_list.items():
for neighbor in neighbors:
print(f"顶点 {vertex} 和顶点 {neighbor} 之间有边")
希望这些信息对你有所帮助!
领取专属 10元无门槛券
手把手带您无忧上云