图数据结构

提示

1. 图数据结构概述：图数据结构由一系列相互连接的节点（称为顶点）组成，每个节点包含数据，并通过边与其他节点相连。例如，Facebook 的图数据结构包含用户、照片、群组等作为节点，这些节点通过诸如“好友关系”、“加入群组”等边相连。
2. 图的基本组成：图由顶点集合 V 和边集合 E 构成，边表示为顶点对 (u,v)，用于连接两个顶点。图可以是有向的（边有方向）或无向的（边无方向）。
3. 图的表示方法：图通常以两种方式表示：邻接矩阵和邻接表。邻接矩阵使用二维数组表示顶点之间的连接关系，适用于边密集的图；邻接表使用链表数组表示，每个链表包含与特定顶点相连的所有顶点，适用于边稀疏的图。

图数据结构是一系列节点的集合，这些节点拥有数据并与其他节点相连。

让我们通过一个例子来理解这一点。在 Facebook 上，一切都是一个节点。包括用户（User）、照片（Photo）、相册（Album）、事件（Event）、群组（Group）、页面（Page）、评论（Comment）、故事（Story）、视频（Video）、链接（Link）、笔记（Note）……任何拥有数据的都是一个节点。

每个关系都是从一个节点到另一个节点的边。无论你发布照片、加入群组、点赞页面等，都会为这种关系创建一个新的边。

因此，Facebook 就是这些节点和边的集合。这是因为 Facebook 使用图数据结构来存储其数据。

更准确地说，图是一个数据结构（V, E），由以下部分组成：

• 一系列的顶点 V
• 一系列的边 E，表示为顶点对 (u,v)

在图中，

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

图术语

• 邻接：如果两个顶点之间有边相连，则称这两个顶点是邻接的。顶点 2 和顶点 3 不是邻接的，因为它们之间没有边。
• 路径：一系列边的序列，可以让你从顶点 A 到达顶点 B，被称为路径。0-1、1-2 和 0-2 是从顶点 0 到顶点 2 的路径。
• 有向图：一种边 (u,v) 不必然意味着存在边 (v, u) 的图。这种图中的边用箭头表示，以显示边的方向。

图表示

图通常以两种方式表示：

1. 邻接矩阵

邻接矩阵是一个 V x V 顶点的二维数组。每一行和每一列代表一个顶点。

如果任何元素 a[i][j] 的值是 1，它表示顶点 i 和顶点 j 之间存在一条边。

我们上面创建的图的邻接矩阵是

由于它是一个无向图，对于边 (0,2)，我们还需要标记边 (2,0)；使邻接矩阵关于对角线对称。

在邻接矩阵表示中，边查找（检查顶点 A 和顶点 B 之间是否存在边）非常快，但我们必须为所有顶点之间的每个可能的链接（V x V）预留空间，所以它需要更多的空间。

2. 邻接表

邻接表表示将图表示为一个链表数组。

数组的索引表示一个顶点，其链表中的每个元素表示与该顶点形成边的其他顶点。

我们在第一个例子中制作的图的邻接表如下所示：

邻接表在存储方面效率较高，因为我们只需要存储边的值。对于拥有数百万顶点的图，这意味着可以节省大量空间。

图操作

最常见的图操作包括：

• 检查元素是否存在于图中
• 图遍历
• 向图中添加元素（顶点、边）
• 寻找从一个顶点到另一个顶点的路径