上查看所有课程
图数据结构是一组具有数据并与其他节点连接的节点。
让我们通过一个例子来理解这一点。在 Facebook 上，一切都是一个节点。包括用户、照片、相册、事件、群组、页面、评论、故事、视频、链接、笔记……任何带有数据的东西都是一个节点。
每个关系是从一个节点到另一个节点的边。无论您是发布照片、加入群组、点赞页面等，都会为该关系创建一个新边。
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. 邻接表
邻接表将图表示为链表数组。
数组的索引代表一个顶点，其链表中的每个元素代表与该顶点形成边的其他顶点。
我们第一个示例中制作的图的邻接表如下：
邻接表在存储方面很高效，因为我们只需要存储边的值。对于拥有数百万个顶点的图，这可以节省大量空间。
图操作
最常见的图操作是：
- 检查元素是否在图中
- 图遍历
- 将元素（顶点、边）添加到图中
- 查找一个顶点到另一个顶点的路径