有向图和无向图的邻接矩阵有什么区别

发布网友发布时间：2022-04-20 04:43

我来回答

共3个回答

热心网友时间：2023-07-10 03:25

一、对称区别：

1、无向图的邻接矩阵是对称的。

2、有向图的邻接矩阵不一定对称。

二、元素区别：

1、对于无向图，顶点V1的度是邻接矩阵中第i行（或第i列）的非零元素的个数。

2、对于有向图，顶点V1的度是邻接矩阵中第i行和第i列的非零元素的个数之和。

扩展资料：

邻接矩阵特点

无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。

无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。

有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。

用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。

参考资料来源：百度百科-邻接矩阵

热心网友时间：2023-07-10 03:26

　　二者的区别：
　　邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：
　　①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
　　②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。
　　③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

热心网友时间：2023-07-10 03:26

0、1和无穷三者不可能同时出现。无向和有向无权图中用1表示能够直接到达，0表示不能一步到达。带权图中正数代表路径权值，无穷表示一步无法到达。追问

这个图的邻接表是下图吗：

那还有这个图：

它的邻接表是这个吗：



追答两个表标注方法不一样。第二个表与书上的一样。第一个虽然能让人看懂，但是不是常规方法：V1点连接V2、V3和V4，按存储位置标号，应该是1、2和3。

首页

文章

有向图和无向图的邻接矩阵有什么区别