邻接矩阵

✍ dations ◷ 2025-07-07 07:09:53 #图论,矩阵,数据结构

在图论中,邻接矩阵(英语:adjacency matrix)是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连,数字的大小可以表示边的权值大小。

距离矩阵可算是邻接矩阵的扩充。

阶为 n {\displaystyle n} 的图 G {\displaystyle G} 的邻接矩阵 A {\displaystyle A} n × n {\displaystyle n\times n} 的。将 G {\displaystyle G} 的顶点标签为 v 1 , v 2 , . . . , v n {\displaystyle v_{1},v_{2},...,v_{n}} 。若 ( v i , v j ) E ( G ) {\displaystyle (v_{i},v_{j})\in E(G)} A i j = 1 {\displaystyle A_{ij}=1} ,否则 A i j = 0 {\displaystyle A_{ij}=0} 。也可以用大于0的值表示边的权值,例如可以用边权值表示一个点到另一个点的距离。

无向图的邻接矩阵是对称矩阵。

可以用矩阵表示为:

这个矩阵中每一行代表一个点,行a即为点a,每一列代表某一行的点所指向的点,矩阵的每一个(小格)表示一条边。图中的所有边(指向性的箭头)带有权值,通常约定权值为0的边为不存在的边。

如此图中的a指向b,箭头旁边的数字(边的权值)为2,在矩阵中表示为行a列b为2。又如矩阵中行c列b为6,图中表现为一条从c指向b权值为6的边。

设图 G {\displaystyle G} 的邻接矩阵为 A {\displaystyle A} ,边的取值为1。

A、B、C、D四人传球6次,从A开始,最终回到A手里,有多少种传法?

非矩阵解法:

矩阵解法:

A = ( 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 ) , A 6 = ( 183 182 182 182 182 183 182 182 182 182 183 182 182 182 182 183 ) {\displaystyle A={\begin{pmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\end{pmatrix}},A^{6}={\begin{pmatrix}183&182&182&182\\182&183&182&182\\182&182&183&182\\182&182&182&183\\\end{pmatrix}}}

邻接矩阵法是比较简单的图论问题建模方法,它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括:

主要缺点包括:

在随机过程理论中,表示单步状态变化的转移矩阵就是一种邻接矩阵。

相关

  • 医药医药是医学和药学的合称,包括:
  • 保泰松保泰松是一种作用于中枢神经系统的药物,属吡唑酮类衍生物,解热镇痛作用较弱而抗炎作用较强,对炎性疼痛效果好,并能促进尿酸的排泄。保泰松的解热镇痛作用不及乙酰水杨酸,且毒性较
  • 有机过氧化物有机过氧化物(英文:Organic peroxide)是含有过氧链(-O-O-)的一类有机化合物,通式为R-O-O-R'。R与R'都为氢时得到过氧化氢(H2O2),有一个为氢时得到氢过氧化物(H-O-O-R)。过酸、过酸酯与
  • 林佑星张晏菻(2013年结婚 2016年离婚) 小妏 (2019年结婚)林佑星(1974年9月6日-),是台湾男演员。早期曾参与中视、华视、民视等连续剧的演出,目前是台湾三立台湾台的主要演
  • 武力武装力量(英语:Armed forces)意为在政府支持下,一个国家拥有武器与兵力的组织性力量。武装力量与军队(military)经常被认为是同义词,但严格意义上来说,这两者间仍有所不同:武装力量除
  • 1786年康定-泸定地震1786年康定-泸定地震发生于1786年6月1日(乾隆五十一年五月初六),震中据推定位于康定与得妥之间,震级为7.75级,震中烈度等于或大于X。此后还有数次余震,直至6月13日停止。此次地震
  • 三角化四面体在几何学中,三角化四面体(英语:triakis tetrahedron或kistetrahedron)是一种卡塔兰多面体,其为截角正四面体的对偶多面体。在矿物学中,这种形状又称为三四面体(英语:tristetrahedron
  • 电动帆电动帆(英语:Electric sail、Electric solar wind sail,簡稱:E-Sail)是一种建议将太阳风作为动压来源的太空飞行器推进方式,其原理为为制造电场来改变太阳风质子的行进方向,进而推
  • 李喜明李喜明(1955年6月24日-),籍贯青岛市,中华民国海军二级上将退役,曾任参谋总长、国防部军政上将副部长(首位现役军人出任者)、海军上将司令、国防部参谋本部中将副参谋总长、海军中将
  • 伊斯兰事务法庭回教法庭是指执行伊斯兰教法的法庭,对马来西亚的每个穆斯林都有管辖权。回教法庭制度是马来西亚法律制度中存在的两个独立的法院制度之一。在家庭法和宗教仪式事宜上只对穆斯