开发者社区> 松伯> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

邻接矩阵学习

简介: 邻接矩阵:是表示顶点之间相邻关系的矩阵。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间的关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
+关注继续查看

邻接矩阵:是表示顶点之间相邻关系的矩阵。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间的关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

设G=(V,E)是一个图,其中V={v1,v2,.....,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:

①对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0,有向图则不一定如此。
②在无向图中,任一顶点i的度为第i列(或第i行)所有非零元素的个数,在有向图中顶点i的出度为第i行所有非零元素的个数,而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间,由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外,仅需要存储上三角形或下三角形的数据即可,因此仅需要n(n-1)/2个空间。
 
特点:
无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵;对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素,故只需1+2+...+(n-1)=n(n-1)/2个单元。
无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度,第i列非零元素的个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非零元素个数之和。
用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。

 

所谓邻接矩阵(Adjacency Matrix)的存储结构,就是用一维数组存储图中顶点的信息,用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n 个确定的顶点,即V={v0,v1,…,vn-1},则表示G 中各顶点相邻关系为一个n×n 的矩阵,矩阵的元素为:

其中,wij 表示边(vi,vj)或<vi,vj>上的权值;∞表示一个计算机允许的、大于所有边上权值的数。

 

用邻接矩阵表示法表示图如图8.7 所示。

用邻接矩阵表示法表示网图如图8.8 所示。

 

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
学习C++笔记137
C++ 运算符
17 0
学习C++笔记133
C++ 运算符
24 0
【机器学习中的矩阵求导】(一)求导布局
然后将每个求导的值排成一个向量表示。类似的结论也存在于标量对向量的求导,向量对向量的求导,向量对矩阵的求导,矩阵对向量的求导,以及矩阵对矩阵的求导等。
37 0
【机器学习中的矩阵求导】(一)求导布局
然后将每个求导的值排成一个向量表示。类似的结论也存在于标量对向量的求导,向量对向量的求导,向量对矩阵的求导,矩阵对向量的求导,以及矩阵对矩阵的求导等。
53 0
【机器学习中的矩阵求导】(五)矩阵对矩阵求导
假如有p×q矩阵F要对m×n的矩阵X求导,根据第一篇求导布局的定义,矩阵F的pq个元素要对矩阵X的mn个值分别求导,所以求导结果一共有mnpq个,求导的结果如何排列:
89 0
【机器学习中的矩阵求导】(九)矩阵论大复习
kron(A,B) 是通过获取 A 元素与矩阵 B 元素之间的所有可能积而形成的一个 mp×nq 矩阵。 先来看一个Python实现Kronecker积等。可以参考numpy的官方文档。
68 0
透明度 | 学习笔记
快速学习透明度。
51 0
学习C#(一)
赶紧好好学学自己的C#,,要不然要给做的东西说拜拜了,,,时间紧迫,,,真担心会食言..................... 在C#中以为只要类有构造方法,,,,原来结构也有 using System; using System.
637 0
邻接矩阵有向图的介绍
邻接矩阵有向图的介绍 邻接矩阵有向图是指通过邻接矩阵表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了",,,,,,,,"共9条边。 上图右边的矩阵是G2在内存中的邻接矩阵示意图。
714 0
C++学习
C++的学习之路比较漫长,自己感觉学习C++应该首先是找一本比较基础的教程书先看一遍多做笔记,然后在多看几本比较基础的C++资料,在有一定的基础的情况下再去看一些晋级的书籍,C++的语法及结构思想学习完之后再涉猎一些关于UML统一建模语言、OOP...
784 0
+关注
松伯
技术专家 专注于大数据领域 博客园地址:https://www.cnblogs.com/yangsy0915/
187
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载