导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
图论是信息学竞赛中非常重要的一部分，这一节课，我们系统讲解信息学竞赛中图论的体系结构，掌握图论的基本概念，了解图的存储结构，了解图的遍历方式，并知道图的几个应用领域。
1 引入
首先我们先来复习一下数组吧。
1 多对多结构
我们在最前面讲数据结构的时候，主要有四种结构：
多对多结构是最复杂的结构，比如班上的同学，同学之间可能有多种关系交叉存在，比如，A和B是亲戚，B和C是舍友，C和D和E是学习小组……
在这些关系中，大家都是等价的，但是对于每个用户自己来说，他们自己对应了多个其他用户。
多对多结构我们将其称之为图结构，这个图，和我们数学上描述的几何图不同，几何图研究的是形状，大小。这里的图，我们称之为拓扑图，我们只研究图上节点和节点之间的关系。
例如，我们图中有三个节点，每个节点之间都有关系，那他们之间的关系可以表示为：
在几何图中，这三个图是完全不一样的，但是在拓扑图中，这三个图表示的都是三个节点，两两之间有关系，所以是一样的。
2 图论结构体系总览
在信息学中，图论主要研究图中节点的相关关系，主要包括：
在下面，我们一起来看一下相关的概念。有关图的基本概念，大家也可以点击文末的阅读原文看我之前讲解的视频。
2 图论基本概念
我们先来看下图的基本概念吧！
1 什么是图
首先我们来了解一下图。
图是一种数据结构，由顶点集V和边集E组成。|V|表示顶点个数，称为图的阶。
2 图的类型
图有多种分类方式，我们一种一种详细讲解。
1、有向图与无向图
图可以根据边是否有方向分为有向图和无向图。
有向图：图的边有方向（弧，用<v,w>表示，v是弧尾，w是弧头。），只能按箭头方向从一点到另一点。
无向图：图的边没有方向（边，用(v,w)表示）。
例如下图中，(a)是一个有向图，(b)是一个无向图。
2、简单图、多重图与完全图
这三个概念是根据图结点与边的关系定义的结构：
3、稠密图与稀疏图
这两个概念没有太严格的定义，边特别密集的是稠密图，特别稀疏的是稀疏图。
例如下面的图是稀疏图：
下面的图是稠密图：
有一种定义方式是说：
当只有三个顶点的时候，就算是完全图，也只有三条边，远没有达到我们认知中的稠密的概念。
3 图的连通性
图中的顶点可能是和其顶点相连的，可以是和所有顶点都不相连的，这就涉及到连通性的问题。
1、无向图的连通性
在无向图中，从一个顶点到另一个顶点有路径存在，我们就说这两个顶点是连通的。在无向图中任意两点都是连通的，叫连通图。
非常重要的一个结论是：n个顶点的连通图最少有n-1条边。这样的图也可以看做是树结构。
连通图中还有连通分量的概念，连通分量指的是一个无向图图的极大连通子图。
2、有向图的强连通性
有向图和无向图有类似的概念，因为无向图有方向，对边的要求更强，我们称之为强连通，如果有向图中一个顶点A到另一个顶点B有有向路径存在，则称从A到B是连通的，如果从A到B，从B到A都有路径，那就说A顶点和B顶点是强连通的。如果有向图中任意两点都是强连通的，那就说这个图是强连通图。
非常重要的一个结论是：n个顶点的强连通图最少有n条边。这样的图会构成一个单向环结构。
强连通图中也有强连通分量的概念，指的是一个有向图图的极大强连通子图。
4 部分图
部分图指的是图中部分点和边（或弧）构成的图，我们也将这个图称为原图的子图。
子图定义如下：一个图的边集和顶点集是另一个图的边集和顶点集的子集，称前面的图是后面的图的子图。
既然能够构成图，那么一定要求子图中的边（或弧）的两个顶点是子图中的顶点。
如果子图的顶点和原图的顶点是一样的，那么我们称这个子图为生成子图。
如果该子图是一个树结构，那么我们称这个子图为生成树。
生成子图在子图的基础上增加了一条要求：包含原图的全部顶点。生成树在生成子图的基础上增加了一条要求：边最少，即不存在回路。
能够构成生成树的前提是这个图是连通图，如果图不连通，我们只能针对图的每个连通分量独立获得生成树，所有的连通分量的生成树构成的，我称之为生成森林。
5 图的度与权
针对于图中的边（或弧），我们有两个非常重要的概念：
1、度
顶点的度指的是图中与该顶点相连的边的数目。
例如下面的图，图中1的度为4：
针对有向图，我们还要细分为入度和出度：
不管是起点还是终点，这些弧都会与该顶点相连，所以我们有：
例如图中1的入度为1（从5入），出度为3（出到2,、3、4）。
特别要强调，入度和出度是针对有向图说的，无向图中没有入度和出度的说法。无向图中，全部顶点度之和等于边数的两倍。这是因为每条边会被其相连的两个顶点各计数一次。每条边都计数两次。
举个例子：下列选项中，正确的是（），错误的是（）
大家先思考，然后点击下面查看答案：
(点击空白处查看答案)
▼
对于A，无向图中，所有顶点的度之和为边数的两倍，所以是偶数，正确。
对于B，无向图没有入度和出度的概念，错误。
对于C，无向图的单个顶点，如果只有一个顶点和这个顶点相连，那这个顶点的度就为1，正确。
对于D，n个顶点的有向图，最多情况下，某个顶点有n-1条弧指向另外n-1个顶点，并且有n-1个指向该顶点的弧，所以度最多为2n-2，错误。
对于E，有向图中，所有顶点的入度=所有顶点的出度=边数，所以所有顶点的入度+所有顶点的出度是边数的两倍。
2、权
权代表的是权重，在图的边（或弧）上可能会包含具有某些含义的数值，比如两个顶点的距离等等。一个带权重的图，我们称之为网。
如下图，这两个顶点之间的边的权重为5。
6 路径、回路与距离
考虑节点到节点，我们有路径的概念，在图论中，路径是指：从一个顶点到另一个顶点之间经过的顶点序列。路径长度是说路径上边的数目。
例如对于上面的图，从A到D的路径可以如下：
大家发现了最后一条路径我们重复走了顶点和边，如果我们不重复走顶点和边，我们就称之为简单路径。
如果我们路径的起点和终点是同一个点，我们称之为回路。如果回路中除了起点和终点外，不重复走顶点和边，我们就称之为简单回路。
两个顶点之间的最短路径，称为距离。
3 图的存储结构
这节课，我们先来简单了解图的存储结构，下节课我们会深入了解，并通过编程实现！
1 邻接矩阵
邻接矩阵是图的顺序结构表示。
我们定义一个二维数组：
其中，G[i][j]的值，表示从点i到点j的边的权值，如果图是无权图，取值为1和0，1表示i和j之间有直接连边，0表示i和j之间没有直接连边。如果图是带权图，当i和j之间有直接连边时，我们存放的是边的权重，如果没有直接连边，我们存放无穷大。
例如对于下面的无向无权图，得到的邻接矩阵：
对于下面的有向带权图，得到的邻接矩阵：
对于无向图来说，从i到j和从j到i是一样的，我们可以采用一维数组压缩存储，在下节课，我们会详细讲解。
2 邻接表与逆邻接表
对于边相对较少的图来说，采用邻接矩阵太浪费空间，我们可以通过链式结构存储图。
对于无向图来说，我们可以对每个顶点，通过链表存放其可以相连的顶点。
其中第一列可以是一个顺序表，存放所有顶点，然后每个顶点有三个部分：
后面的顶点也是三个部分，很多情况下，后面的几列的中间存放数据部分会不要。以A为例，A后面指向的第一个B是和A相连的第一个顶点，然后B的第三个部分指向C，说明C是和A相连的第二个顶点。C的第三个部分是空，表示的是A没有其他相连的顶点了。
对于有向图来说，我们用邻接表存放每个顶点的出度：
这个时候我们能通过邻接表知道每个顶点能去到哪个顶点，但是不能直接知道这个顶点从哪个顶点来，只能遍历所有顶点。这样效率太低了，逆邻接表应运而生。
逆邻接表用来存储有向图的入度：
3 十字链表
对于有向图来说，邻接表只能存出度，逆邻接表只能存入度。使用会受限。
我们能不能将入度和出度都存下来呢？这个时候，十字链表应运而生。
首先十字链表的第一列也是一个顺序表，表示所有的顶点，每个顶点有四个部分：
对于后面的几列，每一个节点表示一条边，包含四个部分：
下图是一个具体示例，为了方便，我们在图中不显示数据域（第一列的第二部分）。
这个时候我们发现横着的指针是出度，竖着的指针是入度。两个指针的指向刚好十字交叉，所以我们将其称为十字链表。
4 图的遍历简述
图最基本最重要的概念之一就是遍历！图有两种最常用的遍历方式：
这两种遍历方式，会对应后面的深度优先搜索（DFS）和广度优先搜索（BFS）两个搜索算法，具体的细节，我们在后面会再讲，这里我们先简单介绍。我们以下图为例说明。
1 深度优先遍历
深度优先遍历，就是一直往下找，只要找得到就一直找下去，就是不断往“深”找。
例如我们从A点开始找，A和B相邻，所以我们遍历B，然后我们考虑和B相邻的顶点，A点已经遍历过，我们接着遍历C，然后我们考虑和C相邻的顶点，比如D。
大家会发现，我们这个过程使用了栈结构。我们从A开始访问，将A入栈，当前栈顶为A，然后我们访问和A相邻的且没有访问过的。然后我们访问B，将B入栈，当前栈顶为B，然后我们访问和B相邻的且没有访问过的。然后我们访问C，将C入栈，当前栈顶为C，然后我们访问和C相邻的且没有访问过的。然后我们访问D，将D入栈，当前栈顶为D，然后我们访问和D相邻的且没有访问过的。然后我们访问E，将E入栈，当前栈顶为E，然后我们访问和E相邻的且没有访问过的。然后我们访问F，将F入栈。这个时候我们发现，访问次数和定点数相同，就可以停止了。
除了上面的停止方式，我们还可以采用如下方式，当访问到F发现和F相邻的全都访问完毕，然后我们就可以将F出栈，F出栈后的栈顶是E。然后看和E相邻的，发现和E相邻的全都访问完毕，然后我们就可以将E出栈，E出栈后的栈顶是D……直到栈为空。
如果这个图是连通图，我们通过这种方式就可以遍历所有的顶点。
如果这个图不是连通图，我们可以接着访问未访问顶点，重新入栈。
2 广度优先遍历
广度优先遍历就是访问一个顶点，就把这个顶点的所有相连的其他顶点都访问。
例如我们访问A，A和BC相连，所以我们就访问B和C，访问完A后，因为B访问了，所以我们访问和B相连且没有访问的，我们访问E，这个时候B也访问完了，还有C的，C和D相连，所以我们访问D。
这个过程是队列结构。
我们先让A入队，然后队头元素是A。我们将和队头相连的顶点入队，BC入队。然后队头元素出队。此时队列为：
继续上述操作，队头元素为B，我们将和队头相连且未访问的顶点入队，E入队。然后队头元素出队。此时队列为：
继续上述操作，队头元素为C，我们将和队头相连且未访问的顶点入队，D入队。然后队头元素出队。此时队列为：
继续上述操作，队头元素为E，我们将和队头相连且未访问的顶点入队，F入队。然后队头元素出队。此时访问顶点个数等于顶点总个数，我们可以退出循环。
我们也可以和深度优先遍历一样，等到队空再结束。因为顶点是存在顺序表中的，所以我们不用担心图非连通的问题。
5 图的应用简述
了解了最基本的图论理论和相关遍历方式，接下来就是图的几个应用！在信息学竞赛中，比较常用的应用如下：
这些概念涉及到的知识点太多，我们没有时间展开讲，有兴趣的同学可以关注我的哔哩哔哩水亦心824查看，也可以点击阅读原文了解整个图论体系。
6 竞赛中的图理论
掌握了图论的基本理论，我们就可以做一些信息学竞赛初赛的真题了！
1 NOIP2011普及组
无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 G 有 7 个顶点， 则它共有（ ）条边；
【分析】
因为是无向完全图，所以每两个顶点之间都要有一条边，一共有7个顶点，每个顶点都会和另外6个顶点相连。所以是7×6=42。但是这样任意两个顶点的边就计算了两次，因为是无向图，所以需要42÷2=21条边，选择B。
2 NOIP2011普及组
对一个有向图而言， 如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，有图就是一个强连通图。事实上，在删掉边（ ） 后，它依然是强连通的。
【分析】
我们先将每个顶点标符号以区分：
然后，我们分别考虑删除四条边，看下哪个会受影响。
首先我们先考虑删除a，就是删除了从B到A的直接的路径，但是我们依然存在路径B-C-A可以从B到A。所以删除a是不影响的。
在竞赛中，我们就不用往下看了。直接选择A。
然后我们考虑删除b，就是删除了从B到C的直接的路径，但是这个时候没有其它路径可以从B到C。所以删除b是会影响的。
然后我们考虑删除c，就是删除了从E到B的直接的路径，但是这个时候没有其它路径可以从E到B。所以删除c是会影响的。
然后我们考虑删除d，就是删除了从D到E的直接的路径，但是这个时候没有其它路径可以从D到E。所以删除d是会影响的。
7 作业
本节课的作业，就是复习上面的所有知识，并完成下面两道题目！
1 NOIP2013普及组
在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。
2 NOIP2013普及组
以 A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）
AI与区块链技术
长按二维码关注