邻接矩阵及其性质

邻接矩阵

邻接矩阵用于表示图。我们可以使用邻接矩阵表示有向图和无向图。以下是邻接矩阵的关键属性。

性质

  • 邻接矩阵A[V][V]是一个大小为V × V的二维数组，其中V是无向图中顶点的数量。

  • 如果Vx和Vy之间存在一条边，则A[Vx][Vy] = 1，且A[Vy][Vx]=1，否则值为零。

  • 对于有向图，如果Vx到Vy之间存在一条边，则A[Vx][Vy]=1，否则值为零。

无向图的邻接矩阵

让我们考虑下面的无向图并构造其邻接矩阵：

Adjacency undirected

上面无向图的邻接矩阵将是：



a
b
c
d
a
0
1
1
0
b
1
0
1
0
c
1
1
0
1
d
0
0
1
0

有向图的邻接矩阵

让我们考虑下面的有向图并构造其邻接矩阵：

Adjacency directed

上面有向图的邻接矩阵将是：



a
b
c
d
a
0
1
1
0
b
0
0
1
0
c
0
0
0
1
d
0
0
0
0

更新于：2019年8月22日

2K+浏览量

开启您的职业生涯

完成课程获得认证

开始学习
广告