邻接矩阵是什么

维基 问答 2022-06-02 13:55:30 阅读(...)

邻接矩阵(adjacency matrix)是一种方阵,用来表示有限图。它的每个元素代表各点之间是否有边相连。图的关联矩阵需要和邻接矩阵区分。

在图论和计算机科学中,邻接矩阵(adjacency matrix)是一种方阵,用来表示有限图。它的每个元素代表各点之间是否有边相连。

邻接矩阵 Adjacency Matrix

作为特例,简单图的邻接矩阵是(0,1)矩阵并且对角线元素都为 0。无向图的邻接矩阵是对称矩阵。图和其邻接矩阵的特征值和特征向量之间的关系是谱图理论的研究对象。

图的关联矩阵需要和邻接矩阵区分。它是图的另一种矩阵表示方式,它的元素表示各个节点-边对是否相关。还有图的度数矩阵,含有每个结点的度数信息。

逻辑结构分为两部分:V 和 E 集合,其中,V 是顶点,E 是边。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

定义

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设 G=(V,E)是一个图,其中 V={v1,v2,…,vn}。G 的邻接矩阵是一个具有下列性质的 n 阶方阵:

1.对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为 0,有向图则不一定如此。

2.在无向图中,任一顶点 i 的度为第 i 列(或第 i 行)所有非零元素的个数,在有向图中顶点 i 的出度为第 i 行所有非零元素的个数,而入度为第 i 列所有非零元素的个数。

3.用邻接矩阵法表示图共需要 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 列非零元素个数之和。

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

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 电视机 Television

    如何测量电视机尺寸

    先准备一个卷尺,把卷尺从屏幕的左上角量到右下角,量出屏幕对角线的长度,一般以厘米为单位【1英寸=2.54厘米】,然后用所量的数字除以2.54就能得出电视尺寸了。
  • Windows11

    安装Windows11需要满足哪些要求

    必须已安装 Windows10的 2004 ,才能升级,处理器1GHz或更快的支持64位的处理器双核或多核或系统单芯片,内存4GB,存储64GB或更大的存储设备,系统固件支持 UEFI 安全启动,显示器对角线长大于 9 英寸高清显示屏。
  • 拍摄

    如何通过简单的技巧拍出高逼格照片

    亮点背景与主体剪影的强对比画面相结合,可以说是最容易拍摄广阔效果的方法。如果想拍摄的场景中,主体不止一个,建议用斜角对齐组织画面。尤其是在拍摄静物和人物时,可以将物体和人物分别在画面对角线两侧,从而达到视角重量均衡的画面效果。
  • 华为手机 HUAWEI Phone

    华为手机如何隐藏图标

    手机桌面上用两根手指由外向内呈对角线滑动,在出现的界面里,可以添加隐藏的应用。需要解除隐藏可在隐藏的应用界面下,点击添加,进入添加界面之后,将隐藏应用上的蓝色符号去掉即可。
  • rar 文件 Rar file

    rar文件如何打开

    打开rar文件首先下载安装WinRAR软件,然后鼠标左键双击打开rar文件,找到并点击【解压到】按钮,接着再选择解压后的存放位置,点击【确认】即可进行解压,最后在设置的存放位置处即可看到解压后的文件。
  • 微信 WeChat

    微信支付密码忘了怎么办

    找回微信支付密码首先打开微信,选择我,找到服务,点击钱包,点击支付设置,点击忘记支付密码,点进去输入个人信息,选择下一步,根据页面提示重新绑定原卡,或添加新的银行卡重置支付密码,根据提示输入信息,就可以设置支付密码,设置完后点击完成即可。