图

一、图（Graph）是什么？

图是由顶点（Vertex）​​ 集合和边（Edge）​​ 集合组成的数据结构，用于表示事物及其之间的关系。

• ​顶点​：代表事物或对象（例如，城市、人、网页）。

• ​边​：代表顶点之间的关系（例如，城市之间的道路、人与人之间的朋友关系、网页之间的超链接）。

数学上记为：G = (V, E)，其中 V是顶点集，E是边集。

二、图的分类

1. 无向图（Undirected Graph）

边没有方向的图。边 (A, B)表示顶点 A 和 B 是相互连接的。

• ​例子​：社交网络中的好友关系（如果 A 是 B 的朋友，那么 B 也一定是 A 的朋友）。

• ​表示​：边用圆括号或无序对表示：(A, B)或 {A, B}。

2. 有向图（Directed Graph / Digraph）

边有方向的图。边 <A, B>（或 A -> B）表示关系从顶点 A ​指向顶点 B。

• ​例子​：微博的关注关系（A 关注 B 并不意味着 B 也关注 A）、网页的超链接。

• ​表示​：边用尖括号或有序对表示：<A, B>或 (A, B)。

3. 带权图（Weighted Graph）

边拥有一个相关联的数值（权重）的图。这个数值可以代表距离、成本、时间等。

• ​例子​：地图上城市之间的道路，权重是距离或通行时间。

• ​表示​：无向带权图和有向带权图都很常见。边通常表示为 (A, B, w)或 A -w-> B。

三、图的相关概念

1. 度（Degree）

• ​无向图中​：顶点 v的度是指与它相连的边的条数。例如，上图中顶点 B 的度是 3。

• ​有向图中​：度分为入度和出度。

  • ​入度（In-degree）​​：指向该顶点的边的数量。​​（有多少边指向我）​​

  • ​出度（Out-degree）​​：从该顶点指出的边的数量。​​（我指向多少边）​​

  • 总度 = 入度 + 出度。

​例子​：在下方的有向图例子中：

• 顶点 B 的入度是 2（有两条边从 A 和 C 指向它）。

• 顶点 B 的出度是 1（它有一条边指向 C）。

四、图的存储方式

如何将图结构存入计算机？主要有两种方式：

1. 邻接矩阵（Adjacency Matrix）

使用一个 V x V的二维数组 matrix来表示图。

• matrix[i][j]的值表示顶点 i和顶点 j之间的关系。

• ​对于无向图​：如果 i和 j之间有边，则 matrix[i][j] = matrix[j][i] = 1（或权重）。矩阵是对称的。

• ​对于有向图​：如果存在边 i -> j，则 matrix[i][j] = 1（或权重），matrix[j][i]则表示 j -> i，是另一条边。矩阵不对称。

• ​对于带权图​：matrix[i][j]存储权重，无连接的地方用 0 或 ∞（无穷大）表示。

​例子​（上方无向图的邻接矩阵）：

​优缺点​：

• ​优点​：

  • 直观，易于理解和实现。

  • 可以快速判断任意两个顶点之间是否有边（O(1)）。

• ​缺点​：

  • 非常浪费内存空间，空间复杂度为 O(|V|²)。对于顶点多、边少的稀疏图，大部分空间被 0 占据。

2. 邻接表（Adjacency List）

为每个顶点建立一个链表​（或数组），存储所有与它直接相连的顶点（对于带权图，还会存储权重）。

• ​对于无向图​：一条边 (A, B)会同时出现在顶点 A 和顶点 B 的邻接表中。

• ​对于有向图​：边 A -> B只会出现在顶点 A 的邻接表（出边表）中。如果想快速求入度，可以额外建立一个逆邻接表​（入边表）。

​例子​（上方无向图的邻接表）：

A -> [B, C]
B -> [A, C, D]
C -> [A, B]
D -> [B]

​优缺点​：

• ​优点​：

  • ​节省空间。空间复杂度为 O(|V| + |E|)，特别适合稀疏图。

  • 能高效地遍历一个顶点的所有邻居，这是很多图算法（如BFS, DFS）的核心操作。

• ​缺点​：

  • 无法像邻接矩阵那样快速判断任意两点 (i, j)是否有边，需要遍历 i的链表（O(degree(i))）。

总结与对比

在实际应用中，如社交网络、地图导航，图通常非常稀疏（每个人的好友、每个城市连接的道路远少于城市总数），因此邻接表是更常用、更高效的选择。