第 20 关 | 图算法——中看不中用：1. 青铜挑战

我们平时在工作、学习中会大量使用图结构，不过呢在使用代码进行具体实现的时候极少使用图，主要是图里容易产生环，难以处理。
在算法里，考察图也不是很多，主要是图的表示非常复杂，初始化一个图就需要几十行代码，非常不利用面试。
不过呢，在笔试、校招等场景还是可能考察图，所以为了提高自己的胜算，我们有必要掌握必要的图问题。

关卡名	常见图算法	我会了✔️
内容	1.理解图的基本特征和常见概念	✔️

前面我们学了线性表和树，线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱也就是父节点，当我们需要表示多对多的关系时，就用到了图。

1. 认识图

图是一种数据结构，其中结点可以具有零个或多个相邻元素，两个结点之间的连接称为边，结点也可以称为顶点。最典型的就是地铁线路图:

为了方便处理，我们会将图抽象为只有顶点(vertex)和边的结构(edge)，如下图所示：

根据边是否有向，可以将图分为有向图和无向图。而根据顶点之间的边是否有权重，又分为带权图和不带权的图。

而不同顶点之间能够连通的线路就称为路径(Path)，例如在上述中间有向图中C到D的路径为”C->B->D“，但是从D到C则没有路径，这称为两个结点不可达。

图结构常用来存储逻辑关系为“多对多”的数据。比如说，一个学生可以同时选择多门课程，而一门课程可以同时被多名学生选择，学生和课程之间的逻辑关系就是“多对多”。再举个例子，{V1, V2, V3, V4} 中各个元素之间具有的逻辑关系如下图所示：

A->B 表示 A 和 B 之间存在单向的联系，由 A 可以找到 B，但由 B 找不到 A。

上图中，从V1可以找到V3、V4、V2，从 V3、V4、V2也可以找到 V1，因此元素之间具有“多对多”的逻辑关系，存储它们就需要用到图结构。

和链表不同，图中存储的各个元素被称为顶点（而不是节点）。拿上图来说，图中含有4个顶点，分别为顶点 V1、V2、V3 和 V4。

通常情况下，我们习惯用 Vi 表示图中的顶点，且所有顶点构成的集合通常用 V 表示。比如说，图1中顶点的集合为 V={V1, V2, V3, V4}。

上图中各个顶点之间的关系都是双向的，这种情况下我们更习惯用下图来表示各个元素之间的关系：

A-B 表示 A 和 B 之间存在双向的联系，由 A 可以找到 B，同样由 B 也可以找到 A。类似图2这样，各个元素之间的联系都是双向的，这样的图结构称为无向图。如果元素之间存在单向的联系，那么这样的图结构称为有向图，例如：

从上面几个图，我们可以得到两个重要的结论：

图中各个顶点的地位是一样的，各个边的地位也是一样的。我们知道树是有根节点的，其他结点都要严格的满足树的要求，而图中各个顶点的等价的，你可以将任何一个视为起始点，任何一个视为终点
对于无向图，如果一个图有n个顶点，那么最少需要n-1条边，最多有n(n-1)/2条边。例如，n=5时，最少和最多的边如下：

2. 图的基本概念

在系统地学习图存储结构之前，需要了解掌握术语以及它们各自代表的含义。

2.1. 弧头和弧尾

有向图中，无箭头一端的顶点通常被称为"初始点"或"弧尾"，箭头一端的顶点被称为"终端点"或"弧头"。

2.2. 入度和出度

对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）。拿图 2 中的顶点 V1来说，该顶点的入度为 1，出度为 2，该顶点的度为 3。

2.3. (V1,V2) 和 <V1,V2> 的区别

无向图中描述两顶点 V1 和 V2 之间的关系可以用 (V1, V2) 来表示；有向图中描述从 V1 到 V2 的"单向"关系可以用 <V1,V2> 来表示。

由于图存储结构中顶点之间的关系是用线来表示的，因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线，又称为边；同样，<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线，又称为弧。

2.4. 集合 VR

图中习惯用 VR 表示图中所有顶点之间关系的集合。例如，图1中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)}，图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

2.5. 路径和回路

无论是无向图还是有向图，从一个顶点到另一顶点途经的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为"回路"（或"环"）。

在此基础上，若路径中各顶点都不重复，此路径被称为"简单路径"；若回路中的顶点互不重复，此回路被称为"简单回路"（或简单环）。

拿图 1 来说，从 V1 存在一条路径还可以回到 V1，此路径为 {V1,V3,V4,V1}，这是一个回路（环），而且还是一个简单回路（简单环）。

在有向图中，每条路径或回路都是有方向的。

2.6. 权和网

有些场景中，可能会为图中的每条边赋予一个实数表示一定的含义，这种与边（或弧）相匹配的实数被称为"权"，而带权的图通常称为网。例如，图4就是一个网结构：

2.7. 子图

指的是由图中一部分顶点和边构成的图，称为原图的子图。

3. 连通图

前面讲过，图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

顶点之间的连通状态示意图

无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。例如，图 2 中的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。

连通图示意图若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。

前面讲过，由图中部分顶点和边构成的图为该图的一个子图，但这里的子图指的是图中"最大"的连通子图（也称"极大连通子图"）。

如图所示，虽然图 a) 中的无向图不是连通图，但可以将其分解为 3 个"最大子图"（图 b)），它们都满足连通图的性质，因此都是连通分量。

连通分量示意图

提示，图 3a) 中的无向图只能分解为 3 部分各自连通的"最大子图"。

需要注意的是，连通分量的提出是以"整个无向图不是连通图"为前提的，因为如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的。
强连通图

有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图 4 所示就是一个强连通图。

强连通图

与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

强连通分量如上图所示，整个有向图虽不是强连通图，但其含有两个强连通分量。

4. 生成树

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

连通图及其对应的生成树如图所示，图 a) 是一张连通图，图 b) 是其对应的 2 种生成树。

连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。

连通图中的生成树必须满足以下 2 个条件：

1包含连通图中所有的顶点；

2任意两顶点之间有且仅有一条通路；因此，连通图的生成树具有这样的特征，即生成树中边的数量 = 顶点数 - 1。
生成森林

生成树是对应连通图来说，而生成森林是对应非连通图来说的。

我们知道，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是1棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。

上图非连通图和连通分量如图所示，这是一张非连通图，可分解为 3 个连通分量，其中各个连通分量对应的生成树如图所示：

注意，图中列出的仅是各个连通分量的其中一种生成树。

因此，多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。

第 20 关 | 图算法——中看不中用：1. 青铜挑战—认识图结构-灵析社区