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


全屏播放
赞赏支持

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

 

邻接矩阵

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

设图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*...

登录查看完整内容


课后作业

课后习题

 

【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 的路径条数。 


登录后发布评论

暂无评论,来抢沙发