### 无向图的数据结构介绍 无向图是一种由一组顶点（vertices 或 nodes）和连接这些顶点的一系列边（edges 或 links）组成的数据结构[^5]。在这种数据结构中，边是没有方向性的，即如果存在一条从节点 A 到节点 B 的边，则这条边也隐含着可以从节点 B 返回到节点 A。 在实际应用中，无向图可以用来表示多种关系网络，比如社交网络中的朋友关系、城市之间的道路连接等。这种数据结构的核心特点在于它的对称性和连通性。 --- ### Python 实现无向图的基本功能 以下是基于邻接表的方式实现无向图的一个简单例子： #### 邻接表的构建 通过字典来存储每个节点与其相邻节点的关系，其中键为节点名称，值是一个列表或集合，用于保存该节点所连接的所有邻居节点。 ```python class Graph: def __init__(self): self.graph = {} def add_vertex(self, vertex): if vertex not in self.graph: self.graph[vertex] = set() def add_edge(self, u, v): if u in self.graph and v in self.graph: self.graph[u].add(v) self.graph[v].add(u) def remove_edge(self, u, v): if u in self.graph and v in self.graph: self.graph[u].discard(v) self.graph[v].discard(u) def get_neighbors(self, vertex): return list(self.graph.get(vertex, [])) def display_graph(self): for node, neighbors in self.graph.items(): print(f"{node} -> {neighbors}") ``` 上述代码实现了以下几个核心功能： 1. **`add_vertex`**: 添加一个新的顶点到图中。 2. **`add_edge`**: 在两个顶点之间建立一条无向边。 3. **`remove_edge`**: 删除两个顶点之间的边。 4. **`get_neighbors`**: 获取某个顶点的所有邻居。 5. **`display_graph`**: 打印当前图的状态以便于调试或查看。 --- #### 使用示例 下面展示了一个简单的使用场景，创建一个包含几个节点的小型无向图并执行操作： ```python g = Graph() g.add_vertex('A') g.add_vertex('B') g.add_vertex('C') g.add_edge('A', 'B') # 增加边 (A-B) g.add_edge('B', 'C') # 增加边 (B-C) print(g.get_neighbors('A')) # 输出 ['B'] print(g.get_neighbors('B')) # 输出 ['A', 'C'] g.display_graph() # 显示整个图的内容 ``` 运行以上程序将会得到如下输出结果： ``` ['B'] ['A', 'C'] A -> {'B'} B -> {'A', 'C'} C -> {'B'} ``` 这表明已经成功地构建了一张小型无向图，并能够查询任意节点的邻居信息。 --- ### 性能分析与扩展讨论 此方法利用了哈希表（字典）作为底层存储机制，因此查找特定节点的时间复杂度接近 O(1)[^1]。然而，在处理大规模稀疏矩阵时可能需要考虑更高效的压缩技术或者专用库的支持，例如 NetworkX 提供了许多优化后的图形算法支持[^2]。 此外，还可以进一步增强这个类的功能，例如计算最短路径、检测环路是否存在等问题都可以在此基础上逐步完善[^3]。 ---