图的表示

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

• 邻接矩阵
• 邻接表

邻接矩阵

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

无向图的邻接矩阵

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

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

有向图的邻接矩阵

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

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

邻接表

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

Mahesh Parahar

更新于: 2019年8月26日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习