邻接矩阵

✍ dations ◷ 2025-07-08 15:57:31 #图论,矩阵,数据结构

在图论中,邻接矩阵(英语: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}}}

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

主要缺点包括:

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

相关

  • No5f14 7s22, 8, 18, 32, 32, 8, 2第一:641.6 kJ·mol−1 第二:1254.3 kJ·mol−1 第三:2605.1 kJ·mol主条目:锘的同位素锘(Nobelium)是一种人工合成元素,符号为No,原子序为102。
  • 自由语素在语言学上,所谓自由语素是指能够独立存在,无须附于其他语素或词根的语素,与此相对的是规范语素。在完全属于分析语的语言例如汉语中,由于语素最少为单词的形式,全部均能独立存在
  • 美国国家科学奖章(美国)国家科学奖章(National Medal of Science),也称总统科学奖章(Presidential Medal of Science)是由美国总统授予曾在行为与社会科学、生物学、化学、工程学、数学及物理学领域
  • 泰累尔马克斯·泰累尔(英语:Max Theiler,1899年1月30日-1972年8月11日),又译马克斯·蒂勒,南非微生物学家。1951年由于发现黄热病疫苗而获得了诺贝尔生理学或医学奖。1899年1月30日,泰累尔
  • 半乳甘露聚糖半乳甘露聚糖(Galactomannan,简写GM)或称半乳糖甘露聚糖,是一种包含了甘露糖骨干与半乳糖旁基的多糖,更准确的一点来说,半乳甘露聚糖是直线状(1-4)-连结的β-D型甘露糖((1-4)-linke
  • 省财厅广东省财政厅大楼,是广东省广州市的一座著名政府部门建筑物,位于北京路北端,大楼为仿西方古典折衷主义风格。首期工程建成于1919年。1949年后成立的广东省人民政府财政厅,仍延续
  • 国际展览局国际展览局(法语:Bureau International des Expositions,缩写BIE),是协调和审批世界博览会事务的政府间合作组织,总部设于法国巴黎。1928年11月28日,31个国家的代表在巴黎签署了《
  • 南庚南庚(?-?),子姓,名更,中国商朝第十八任君主。沃甲之子,前任君主祖丁之从弟(堂弟)。南庚在位期间将国都由庇迁至奄,因奄地偏南,所以此王得名“南庚”。死后由祖丁之子阳甲继位。现今流传
  • 南阳盆地南阳盆地,又称南襄盆地,是中国内陆中部一个方圆500多里的盆地,是中国人口最多的盆地之一。地跨湖北河南两省,面积约3万平方公里,人口约1500-2000万。该盆地地处二三阶梯分界,南北
  • 伊红Y伊红-Y 是的伊红的一种,是一种生物染色剂,呈淡黄色。伊红-Y是荧光素的四溴衍生物,化学式是C20H6Br4Na2O5。常用在苏木精-伊红染色中,另和百里酚共同用于防止水溶液长霉。铁及含