图论中的基本术语

一幅图结构由若干 节点 (Vertex) 和 边 (Edge) 构成，其中：

• 每个节点有一个唯一 ID。
• 边可以是有向的（有向图，Directional Graph），也可以是无向的（无向图，Undirected Graph）。
• 边上可以有权重（加权图，Weighted Graph），也可以没有权重（无权图，Unweighted Graph）。

边的权重和方向

下图是一个有向无权图：

图中有一条从节点 1 指向节点 3 的有向边，这说明可以从节点 1 直接到达节点 3；但由于没有从节点 3 指向节点 1 的有向边，所以节点 3 不能直接到达节点 1。

下图是一个无向无权图：

图中节点 1 和节点 3 之间有一条无向边，这说明可以从节点 1 到达节点 3，也可以从节点 3 到达节点 1。

你可以把无向图理解成「双向图」，实际上我们在用代码实现图结构的时候就是这么做的。

下图是一个有向加权图：

下图是一个无向加权图：

加权图在实际场景中非常常见，比如在地图 App 中，边的权重可以是两个地点之间的距离；在物流网络中，边的权重可以是两个地点之间的运输成本等等。

围绕着加权图，又会有很多经典的图论算法，比如计算最短路径，最小生成树等等，这些都会在后面的章节逐步讲解。

度

对于图中的每个节点，有一个度 (degree) 的概念。

在无向图中，度就是每个节点相连的边的条数。

比方下面这幅无向图中，节点 1 的度为 2，节点 4 的度为 4。

由于有向图的边有方向，所以有向图中每个节点的度被细分为入度 (indegree)和出度（outdegree）。

比如下图中节点 3 的入度为 2（有两条边指向它），出度为 1（它有 1 条边指向别的节点）：

边和节点的数量关系

我们一般讨论的图结构都是「简单图」，即没有自环边（Self loop）和多重边（Multiple edges）的图。

在简单图中，假设包含 $E$ 条边，$V$ 个节点，我们想一下边的条数 $E$ 的取值范围是多少？

$E$ 的最小值可以是 0，相当于图结构中只有若干互不相连的节点，这是可以的。

考虑 $E$ 的最大值，图中的每个节点最多可以有 $V-1$ 条边与其他 $V-1$ 个节点相连，所以最多能有的边数为 $E = V(V-1)/2 \approx V^2$。

如果 $E$ 接近 $V^2$，我们说这幅图是 稠密图；如果 $E$ 远小于 $V^2$，我们说这幅图是 稀疏图。

子图

在图论中，子图是一个重要的基本概念。

子图 (Subgraph)：如果图 $G'$ 的所有节点和边都包含在图 $G$ 中，则称 $G'$ 是 $G$ 的一个子图。简单来说，子图是从原图中删除一些节点和边后得到的图。

假设上面这幅图为 $G$，我们举例说明子图的概念。子图有两种特殊类型：

生成子图 (Spanning Subgraph)：包含原图中所有节点，但只包含部分边的子图。

下图是图 $G$ 的一个生成子图，它包含了所有节点，但移除了节点 3 和节点 4 之间的边。

导出子图 (Induced Subgraph)：选择原图的一部分节点，以及这些节点之间在原图中的所有边所构成的子图。

下图是图 $G$ 的一个导出子图，它包含节点 1,2,3,4 及它们之间在原图中的所有边。

子图的概念在很多图算法中都有应用，比如在寻找最小生成树时，我们实际上是在寻找一个包含所有节点的带权重最小的生成子图。

连通性

在图论中，连通性是一个非常重要的概念，它描述了图中节点之间是否存在路径。

无向图的连通性

连通图 (Connected Graph): 如果无向图中任意两个节点之间都存在一条路径，我们称这个图是连通的。

上图是一个连通图，从任意一个节点出发，都能到达其他所有节点。

连通分量 (Connected Component)：对于非连通的无向图，其中的多个连通子图被称为连通分量，一个图可以有多个连通分量。

比如下面这幅图有两个连通分量：节点 1~5 形成一个连通分量，节点 6,7 形成另一个连通分量。

有向图的连通性

有向图的连通性概念稍微复杂一些，因为考虑到边的方向，所以有向图的连通性分为强连通和弱连通。

强连通图 (Strongly Connected Graph)：如果有向图中任意两个节点之间都存在一条有向路径，我们称这个图是强连通的。

比如下面这幅图是一个强连通图，从任意节点出发都能到达其他所有节点。

弱连通图 (Weakly Connected Graph)：如果将有向图中的所有有向边都变成无向边后，该图变成连通的，那么原来的有向图就是弱连通的。

比如下面这幅图不是强连通的（无法从节点 4 到达节点 1），但它是弱连通的，因为忽略边的方向后，所有节点之间都是连通的。

强连通分量 (Strongly Connected Component, SCC)：有向图中的若干个最大的强连通子图称为强连通分量。

比如下面这幅图有两个强连通分量：节点 1~3 形成一个强连通分量，节点 4~6 形成另一个强连通分量。

弱连通分量 (Weakly Connected Component, WCC)：将有向图的所有有向边变为无向边后，形成的连通分量称为原有向图的弱连通分量。

图论中还有很多其他的复杂术语，不过对于数据结构和算法的学习，理解上面这些名词就绰绰够用了。后面我们讲到具体的图论算法时，会结合实际场景运用这些概念。