专栏首页个人分享邻接矩阵学习

邻接矩阵学习

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

设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 所示。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Ceph在手,天下我有

    有人问我,你是如何做到统一存储的?我微微一笑,大声告诉他:Ceph在手,天下我有。

    叁金
  • 如何创建私有Python包存储库

    Python包的基本脚手架是一个包含与用户交互的代码的__init__.py文件。

    林纾燊
  • 【安富莱二代示波器教程】第5章 示波器设计—波形快速刷新方案

    波形快速刷新有很多方案需要测试,由于我们的GUI是采用的emWin,所以下面的这些测试都是基于emWin实现的。

    用户2977066
  • Objective-C 内存管理(上)学习笔记

    这里的“计数”表明必然会有一个东西(变量)来记录引用的变化,而在OC里这个变量就是retainCount;那么还有一个问题就是通过什么方式来操作这个变量,OC里...

    半纸渊
  • Kafka 简介

    在Kafka中,客户端和服务器之间的通信是通过一种简单的,高性能的,语言不可知的TCP协议完成的。

    小忽悠
  • 漫谈未来的HDFS

    前面我们提到的HDFS,了解了HDFS的特性和架构。HDFS能够存储TB甚至PB规模的数据是有前提的,首先数据要以大文件为主,其次NameNode的内存要足够大...

    叁金
  • 存储是怎样炼成的?

    什么FAT,NTFS,NFS,DAS,SAN,NAS,OSD这些名词我一个都不认识。

    叁金
  • 数组、List和ArrayList的区别

     有些知识点可能平时一直在使用,不过实际开发中我们可能只是知其然不知其所以然,所以经常的总结会对我们的提高和进步有很大的帮助,这里记录自己在工作之余的问题,持续...

    Rekent
  • 不讲CRUSH的Ceph教程是不完整的

    前面我们提到了Ceph是一个支持统一存储架构的分布式存储服务。简单介绍了Ceph的基本概念和基础架构包含的组件,其中最重要的就是底层的RADOS和它的两类守护进...

    叁金
  • 内存泄露的一些坑

    如上,在Activity内部如果声明一个这样的Handler,那么myHandler就默认持有Activity引用,假设Activity退出了,但是可能这时候才...

    大大大大大先生

扫码关注云+社区

领取腾讯云代金券