python中如何用邻接矩阵建图

python中如何用邻接矩阵建图

作者:William Gu发布时间:2026-01-14阅读时长:0 分钟阅读次数:4

用户关注问题

Q
邻接矩阵表示的优缺点是什么?

我想知道在使用邻接矩阵表示图时,这种方法有哪些优势和不足?

A

邻接矩阵的优缺点

邻接矩阵使用二维数组表示图的边连接关系,优点是查询两节点间是否有边的操作很快,时间复杂度为O(1)。适合稠密图,但缺点是空间复杂度较大,需要存储所有节点之间的连接信息,即使很多边不存在,在节点数多时会消耗较多内存。

Q
如何用Python代码实现邻接矩阵建图?

我需要一段简单示例代码,用Python创建一个邻接矩阵并为图添加边,方便我理解和使用。

A

Python实现邻接矩阵的示例

可以使用二维列表(列表的列表)来表示邻接矩阵。先创建大小为节点数的二维列表并初始化为0,表示没有边。然后根据边的信息,更新对应位置为1或边权重。例如,graph[u][v] = 1表示从节点u到节点v有边。

Q
在邻接矩阵中如何表示无向图和有向图?

我想知道邻接矩阵分别如何表示无向图和有向图,两者在矩阵中有什么区别?

A

邻接矩阵中无向图和有向图的表示方式

有向图中,邻接矩阵中graph[u][v]表示从节点u指向节点v的边存在与否,矩阵不一定对称。而无向图中边是双向的,邻接矩阵必须是对称的,即graph[u][v]和graph[v][u]值相等,表示u和v之间有边连接。