admin 管理员组

文章数量: 1086019


2024年4月21日发(作者：使用微服务的好处)

邻接矩阵和关联矩阵

一、概念解释

邻接矩阵和关联矩阵是图论中常用的两种表示图的方式。

邻接矩阵是指用一个二维数组来表示图中各个节点之间的连接情况，

其中数组的行和列分别代表节点，如果节点i和节点j之间有连边，则

邻接矩阵中第i行第j列的元素为1，否则为0。

关联矩阵是指用一个二维数组来表示图中各个节点和边之间的联系，

其中数组的行代表节点，列代表边，如果节点i与边j有关联，则关联

矩阵中第i行第j列的元素为1或-1，分别表示该节点是边的起点或终

点；如果该节点与该边没有关联，则为0。

二、邻接矩阵

1.构建邻接矩阵

要构建一个无向图G={V,E}的邻接矩阵A（V*V），可以按以下步骤进

行：

（1）初始化A为全0矩阵；

（2）遍历E集合中每一条边(u,v)，将A[u][v]和A[v][u]均设为1；

（3）对角线上所有元素均设为0。

2.应用场景

邻接矩阵适用于稠密图（即节点数较多，边数较多）的存储和计算，

因为其空间复杂度为O(V^2)，而且可以快速判断任意两个节点之间是

否有连边。

3.优缺点

邻接矩阵的优点包括：

（1）易于理解和实现；

（2）空间利用率高；

（3）可以快速判断任意两个节点之间是否有连边。

邻接矩阵的缺点包括：


本文标签： 节点 代表 空间 包括 元素

版权声明：本文标题：邻接矩阵和关联矩阵 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1713676341a646502.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。