图的表示

主要有两种方法来表示图：

  • 邻接矩阵
  • 邻接表

邻接矩阵

邻接矩阵 A[V][V] 是一个大小为 V × V 的二维数组，其中 $V$ 是无向图中顶点的数量。如果在 Vx 和 Vy 之间存在一条边，则 A[Vx][Vy]=1 且 A[Vy][Vx]=1，否则值为零。对于有向图，如果在 Vx 和 Vy 之间存在一条边，则 A[Vx][Vy]=1，否则值为零。

无向图的邻接矩阵

让我们考虑以下无向图并构建其邻接矩阵：

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



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

有向图的邻接矩阵

让我们考虑以下有向图并构建其邻接矩阵：

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



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

邻接表

在邻接表中，一个链接列表的数组 (A[V]) 用于表示具有 V 个顶点的图 G。条目 A[Vx] 表示与第 Vx 个顶点相邻的顶点的链接列表。无向图的邻接表如下所示：


更新于: 2019年8月26日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告