邻接矩阵法
标签: 数据结构
学习人数: 56.1k

图有两种存储方式,邻接矩阵和邻接表。

 

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。

设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

看一个实例,下图左就是一个无向图。

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
 

从这个矩阵中,很容易知道图中的信息。

(1)要判断任意两顶点是否有边无边就很容易了;
(2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。
若图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为

 

小结

1、在简单应用中,可以直接用二维数组作为图的邻结矩阵,如int G[105][105]。

2、无向图的邻结矩阵是对称矩阵,对规模很大的邻结矩阵可采用压缩存储。

3、邻结矩阵表示法的空间复杂度为O(n2),其中n为图的顶点数|V|。

4、用邻结矩阵法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。

5、稠密图适合使用邻结矩阵的存储表示。

6、设图G的邻结矩阵为A,An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

登录查看完整内容


课后作业

课后习题

 

【2013年真题】设图的邻接矩阵 A 如下所示。各顶点的度依次是()

A. 1,2,1,2         B. 2,2,1,1 
C. 3,4,2,3         D. 4,4,2,2

参考答案:C
答案解析:各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。 

 

【2015年真题】已知含有 5 个顶点的图 G 如下图所示。

请回答下列问题: 
1)写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。 
2)求 A2,矩阵 A2中位于 0 行 3 列元素值的含义是什么? 
3)若已知具有 n(n≥2)个顶点的图的邻接矩阵为 B,则 Bm(2≤m≤n)中非零元素的含义是什 
么?

参考答案:
1)图 G 的邻接矩阵 A 如下: 

2)A2如下: 

0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。 
3)Bm(2≤m≤n)中位于 i 行 j 列(0≤i,j≤n-1)的非零元素的含义是:图中从顶点 i 到顶点 j 
长度为 m 的路径条数。 


登录后开始许愿

暂无评论,来抢沙发