[教程]Python中无向图的存储：图论入门，探索常见数据结构及其优缺点

引言在图论中，无向图是一种基本的数据结构，用于表示对象之间的无向连接。在Python中，有多种方式可以存储无向图，每种方法都有其特点和适用场景。本文将介绍几种常见的无向图存储方法，并探讨它们的优缺点。...

引言

在图论中，无向图是一种基本的数据结构，用于表示对象之间的无向连接。在Python中，有多种方式可以存储无向图，每种方法都有其特点和适用场景。本文将介绍几种常见的无向图存储方法，并探讨它们的优缺点。

邻接矩阵

邻接矩阵是一种使用二维数组来表示无向图的方法。矩阵中的元素表示两个顶点之间是否存在边。如果顶点i和顶点j之间存在边，则矩阵的第i行第j列（以及第j行第i列）的元素为1，否则为0。

class AdjacencyMatrix: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, v1, v2): if v1 >= self.num_vertices or v2 >= self.num_vertices: raise ValueError("Vertex index out of bounds") self.adj_matrix[v1][v2] = 1 self.adj_matrix[v2][v1] = 1 def remove_edge(self, v1, v2): if v1 >= self.num_vertices or v2 >= self.num_vertices: raise ValueError("Vertex index out of bounds") self.adj_matrix[v1][v2] = 0 self.adj_matrix[v2][v1] = 0 def is_connected(self, v1, v2): return self.adj_matrix[v1][v2] == 1

优点

• 易于实现和操作。
• 可以快速检查两个顶点之间是否存在边。
• 适合稀疏图。

缺点

• 对于稀疏图，空间效率低。
• 查找边的操作需要O(n)时间复杂度。

邻接表

邻接表是一种使用列表来表示无向图的方法。对于每个顶点，我们创建一个列表，其中包含与该顶点相连的所有顶点。

class AdjacencyList: def __init__(self, num_vertices): self.adj_list = {i: [] for i in range(num_vertices)} def add_edge(self, v1, v2): self.adj_list[v1].append(v2) self.adj_list[v2].append(v1) def remove_edge(self, v1, v2): self.adj_list[v1].remove(v2) self.adj_list[v2].remove(v1) def is_connected(self, v1, v2): return v2 in self.adj_list[v1]

优点

• 对于稀疏图，空间效率高。
• 查找边的操作时间复杂度为O(1)。
• 可以轻松添加和删除边。

缺点

• 查找两个顶点之间是否存在边需要O(n)时间复杂度。

总结

Python中存储无向图的方法有很多，选择哪种方法取决于具体的应用场景。邻接矩阵适用于稀疏图，而邻接表适用于稠密图。在实际应用中，可以根据需要选择合适的方法。