图的邻接表和矩阵表示

尽管它们看起来不同， 图形类型 可以用类似的方式表示。图表示通常有两种类型：

1. 邻接矩阵
2. 邻接表

邻接表

邻接表由链表组成。每个顶点被视为一个数组索引，每个元素代表一个链表。这些链表包含与索引顶点有边的顶点。

以下是邻接表的一个例子：

假设一个图包含 V 个顶点和 E 个边。

一般来说，空间复杂度为 O(V + E).

最坏情况下的空间复杂度将是 O(V2) 如果给定的图是完整图

邻接矩阵

邻接矩阵由二维数组组成。如果图有 V 个顶点，则矩阵的大小为 VxV.

说， matrix[i][j] = 5。这意味着节点 i 和 j 之间存在一条边，其权重为 5。

让我们看看下面的图及其邻接矩阵：

我们创建了 二维阵列 使用这些步骤：

步骤1） 顶点 A 与 B 有直接边，权重为 5。因此，A 行和 B 列的单元格将填充 5。A 行的其余单元格将填充零。

步骤2） 顶点 B 与 C 有直接边，权重为 4。因此，B 行和 C 列的单元格将填充 4。B 行中剩余的单元格将填充零，因为 B 没有到任何其他节点的出边。

步骤3） 顶点 C 与任何其他顶点均无直接边。因此，行 C 将用零填充。

步骤4） 顶点 D 与 A 和 C 有一条有向边。

• 此处，D 行 A 列的单元格的值为 7。D 行 C 列的单元格的值为 2。
• D 行的其余单元格将用零填充。

步骤5） 顶点 E 与 B 和 D 具有有向边。E 行和 B 列中的单元格的值为 6。E 行和 D 列中的单元格的值为 3。D 行中其余单元格将用零填充。

以下是需要注意的几点：

• 当邻接矩阵的主对角线为 0 时，该图没有自循环。
• 如果索引 (a,b) 和 (b,a) 的值不相同，则该图为有向图。否则，该图为有向图。
• 如果单元格的值大于 1，则图表将是加权图表。

邻接矩阵存在一些问题，因为它需要平方空间。在这里，我们存储未连接的边。这些边在内存中分配空间。

例如，如果我们有一个包含 100 个节点的图，则需要 10 个单元来将其存储在 内存。如果图中的边较少，分配这么大的内存可能会浪费。因此，使用邻接矩阵的空间复杂度将是 O(N2)，其中 N 表示图中的节点数。