邻接矩阵和邻接表有什么区别?

如题所述

一、对称区别:

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列非零元素个数之和。

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

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

温馨提示:答案为网友推荐,仅供参考
相似回答