临接矩阵m
邻接矩阵是一个表示图中顶点之间连接关系的矩阵。对于一个无向图或有向图,邻接矩阵是一个方阵,其行和列代表图中的顶点,矩阵中的元素表示顶点之间的连接情况。
无向图的邻接矩阵
对于无向图,如果顶点i和顶点j之间有边相连,则邻接矩阵中第i行第j列(同时第j行第i列,因为是无向图)的元素为1,否则为0。
例子: 考虑一个无向图,包含4个顶点和以下边:
顶点A和顶点B之间有边
顶点A和顶点C之间有边
顶点B和顶点D之间有边
顶点C和顶点D之间有边
这个图的邻接矩阵如下:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
解释:
第一行第二列的1表示A和B之间有边。
第二行第一列的1表示B和A之间有边(因为是无向图,所以A和B之间的边是双向的)。
以此类推,其他位置的1表示相应的顶点之间有边。
有向图的邻接矩阵
对于有向图,邻接矩阵中的元素表示从一个顶点到另一个顶点的有向边。如果顶点i到顶点j有一条有向边,则邻接矩阵中第i行第j列的元素为1,否则为0。
例子: 考虑一个有向图,包含4个顶点和以下边:
顶点A指向顶点B
顶点A指向顶点C
顶点B指向顶点D
顶点C指向顶点D
这个图的邻接矩阵如下:
A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0
解释:
第一行第二列的1表示A指向B。
第二行第四列的1表示B指向D。
以此类推,其他位置的1表示相应的有向边。
邻接矩阵是图论中描述图结构的一种常用方法,它可以用来快速判断两个顶点之间是否有边相连,以及进行图的各种算法分析。