首页 >
邻接矩阵法
✍ dations ◷ 2025-04-04 18:01:39 #邻接矩阵法
在图论中,邻接矩阵(英语:adjacency matrix)是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连,数字的大小可以表示边的权值大小。距离矩阵可算是邻接矩阵的扩充。阶为
n
{displaystyle n}
的图
G
{displaystyle G}
的邻接矩阵
A
{displaystyle A}
是
n
×
n
{displaystyle ntimes 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}}}邻接矩阵法是比较简单的图论问题建模方法,它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括:主要缺点包括:在随机过程理论中,表示单步状态变化的转移矩阵就是一种邻接矩阵。
相关
- 杀外寄生虫药外寄生物感染是指主要由外寄生物引起的寄生虫病。外寄生物即暂时或永久寄生于宿主体表的寄生物。例如:治疗外寄生物感染常使用杀外寄生虫药(英语:ectoparasiticide),以杀死外寄生
- 贾干弟鞭毛虫Lamblia intestinalisGiardia duodenalis蓝氏贾第鞭毛虫(学名:Giardia lamblia)又称蓝布尔吉亚尔氏鞭毛虫、梨形鞭毛虫,简称贾第虫。属于鞭毛虫纲,主要寄生在人体肠道内,引起腹痛
- 全球变暖全球变暖,或称全球暖化,指的是在一段时间中,地球的大气和海洋因温室效应而造成温度上升的气候变化,为公地悲剧之一,而其所造成的效应称之为全球变暖效应。在2013年,政府间气候变化
- 民法大全《民法大全》(Corpus Juris(亦作Iuris) Civilis),又称《查士丁尼法典》或《国法大全》,是东罗马帝国皇帝查士丁尼一世下令编纂的一部汇编式法典,完成于公元529至565年。严格来说,《
- 脊椎驼背后凸症脊椎驼背后凸症(英语:Scheuermann's Disease) 亦称舒尔曼病、舒曼氏症(英语:Sherman's Disease),或绍尔曼病,是一种骨骼性疾病,造成脊椎曲线后凸,发生在胸部脊椎多于腰部脊椎。发生原
- 尼罗-撒哈拉语系尼罗-撒哈拉语系分布于非洲的尼罗河沿岸,尼日尔河沿岸以及非洲中部的撒哈拉地区,包括了中苏丹语族、东苏丹语族、撒哈拉语族、桑海语族、马巴语族等语族。多为声调语言,名词有
- 页面构成原理页面构造原理是书籍设计中用来描述页面比例, 书籍中空白和文字区域的构成的一套原则.在20世纪中末期 扬·奇肖尔德 在前人 J. A. van de Graaf, Raúl M. Rosarivo, Hans Ka
- 托马斯·布朗托马斯·布朗爵士(Sir Thomas Browne,1605年10月19日-1682年10月19日),英国作家,对医学、宗教、科学和神秘学都有贡献。布朗的作品显示出他对自然世界的强烈兴趣,并且受到培根科学
- 吡哆醇吡哆醇(英语:Pyridoxine)是一种被称为维生素B6的化合物之一,另外两个分别是:吡哆醛与吡哆胺。它与吡哆胺的不同在于4位取代基。它也常被用作“吡哆醇盐酸盐”。化合物基于吡啶环,
- HAt砹化氢,又称氢砹酸(化学式:HAt),是一种卤氢酸,由氢原子与砹原子组成的共价化合物。这种化合物溶于水生成氢砹酸,性质和其他四种卤化氢相似——实际上具备氢卤酸中最强的酸性。但它