邻接矩阵构建图 python

### 使用 Python 构建基于邻接矩阵的图在图论中，邻接矩阵是一种常用的表示方法。它通过一个二维数组来描述节点之间的连接情况。如果存在从节点 \(i\) 到节点 \(j\) 的边，则邻接矩阵中的位置 \((i, j)\) 将被标记为 1 或其他权重值；否则，该位置通常设置为 0。以下是利用 Python 创建并操作基于邻接矩阵的图的具体实现： #### 定义类 `Graph` 来封装图的功能下面展示了一个简单的 `Graph` 类定义，其中包括初始化、打印邻接矩阵以及添加边的方法。 ```python class Graph: def __init__(self, vertices): self.vertices = vertices # 节点的数量 self.adj_matrix = [[0] * vertices for _ in range(vertices)] # 初始化邻接矩阵 def add_edge(self, u, v, weight=1): # 添加有向边，默认权值为1 if 0 <= u < self.vertices and 0 <= v < self.vertices: self.adj_matrix[u][v] = weight else: raise IndexError("Vertex index out of bounds") def display_adj_matrix(self): # 打印当前的邻接矩阵 for row in self.adj_matrix: print(row) # 测试代码 g = Graph(4) # 建立具有四个顶点的图 edges = [(0, 1), (0, 2), (1, 2), (2, 3)] for edge in edges: g.add_edge(edge[0], edge[1]) g.display_adj_matrix() ``` 上述代码片段展示了如何创建一个基本的无权图，并将其转化为邻接矩阵形式[^1]。对于加权图的情况，只需修改 `add_edge()` 方法，在调用时传入额外参数即可指定每条边对应的权重。需要注意的是，当处理大规模稀疏网络时，采用邻接矩阵可能会浪费大量存储空间，因为大部分元素都保持零状态。此时应考虑改用更节省内存的数据结构——比如 **邻接表** ——来进行优化[^2]。 #### 高效查询两点间的关系由于访问数组索引所需时间为常量级复杂度 O(1)，因此借助邻接矩阵能够快速判断任意两结点是否相连。然而这种优势是以牺牲遍历整个行或列寻找特定邻居所需的线性时间成本(O(n))作为代价的。 ---

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇吃桃问题python头歌