【数据结构】图解图论：度、路径、连通性，五大概念一网打尽

导读

大家好，很高兴又和大家见面啦！！！

在上一篇中，我们初步认识了图的定义与分类。今天，我们将深入探讨图的核心概念： • 顶点的度（无向图与有向图的入度、出度） • 路径与回路（简单路径、简单回路、路径长度的计算） • 距离与连通性（连通图、强连通图的判断） • 子图与连通分量（生成子图、极大连通子图）

通过生活化示例与图解，助你轻松掌握图的基础逻辑。让我们开始吧！

一、顶点的度

在无向图中，顶点v的度是指依附于顶点v的边的条数，记为 TD(v)。

在有向图中，顶点v的度分为入度和出度：

• 入度是以顶点v为终点的有向边的数目，记为ID(v)
• 出度是以顶点v为起点的有向边的数目，记为OD(v)
• 顶点v的度为入度与出度之和，即 TD(v) = ID(v) + OD(v)

在有向图中，全部顶点的入度和与出度和相等，并且等于边数，这是因为每条有向边都有一个顶点和一个终点。

二、路径

路径：是两个顶点之间的所有顶点组成的顶点序列

graph LR
A---B---C---D---E---A

在上图中，因为该图为无向图，所以顶点B到顶点E的路径有两条：

• 路径1：B, C, D, E
• 路径2：B, A, E

而在有向图中，路径的方向应与弧的方向保持一致：

graph LR
A-->B-->C-->D-->E-->A
B-->A

例如上图中，B到E的路径只有一条：B, C, D, E

这是因为B和A之间存在弧 <B, A><A, E>

这就好比生活中的自来水厂供水，我们平时用的自来水都是自来水厂通过自来水管道向我们提供，该管道是一个单向管道，自来水只能从水厂流动到我们家里，我们无法从家里将自来水流回到自来水厂。

graph LR
A[自来水厂]--->B[住宅]
A--->C[公寓]
A--->D[办公楼]
A--->E[商城]

在一条路径中，与其相关联的边我们可以将其理解为路径的构成要素。即只有两个顶点有将其相连接的边（或者弧）那这两个顶点之间才会存在路径：

graph LR
A---B---C---D---E---A
F
a-->b-->c-->d-->e-->a
b-->a

就比如上图中，顶点F与其它顶点之间都没有与之相连的边或弧，因此顶点F与其它顶点之间不存在路径。

回路：第一个顶点与最后一个顶点相同的路径就是回路，也称为环。

就比如在上面的有向图中，存在一条回路为：a, b, a，或者上面的无向图中，每个顶点都存在两条回路，以点A为例：

• 回路1：A, B, C, D, E, A
• 回路2：A, E, D, C, B, A

简单路径：在路径序列中顶点不重复出现的路径称为简单路径。

简单的来说就是在路径中不存在回路，这里我们有向图为例：

graph LR
A-->B-->C-->D-->E-->A
C-->B

在上图中，顶点A到顶点E存在以下路径：

• 路径1：A, B, C, D, E
• 路径2：A, B, C, B, C, D, E

这里的路径1就是简单路径，路径2中存在顶点B与顶点C的回路，因此不是简单路径。

简单回路：在回路中，除了第一个顶点和最后一个顶点外，其它顶点都不重复出现。

这里我们还是以这个图为例：

• 回路1：A, B, C, D, E, A
• 回路2：A, B, C, B, C, D, E, A

在这两个回路中，回路1就是只有第一个顶点和最后一个顶点相同，因此它就是简单回路；

在回路2中，除了第一个顶点与最后一个顶点外，还存在其它重复的顶点，因此它不是简单回路。

路径长度：路径上的边的数目称为路径长度。

在前面的回路1中，其路径长度为：5；在回路2中，其路径长度为7。

三、距离

距离：距离指的是顶点到顶点之间的最短路径。

graph LR
A---B---C---D---E---A
A---D
F

我们以上图的无向图为例，顶点A到顶点E总共有以下简单路径：

• 简单路径1：A, B, C, D, E
• 简单路径2：A, D, E
• 简单路径3：A, E

其中，最短路径为简单路径3——A, E，其路径长度为1，因此顶点A到顶点E的距离为1。

那对于顶点A到顶点F呢？它们之间的距离又是多少？

从图中我们不难发现，这两个顶点之间并没有将其连接的边，也就是说，我们无法从A到达F，也没办法从F到达A，因此我们可以说他们之间的距离为 \infty 。

这个怎么理解呢？

在无向图总，边就是连接两个顶点之间的桥梁，这就好比两座孤岛，如果这两座孤岛之间存在能够相互联系的方式，如桥梁、船、飞机、潜艇……，只要存在，不管是哪种方式都行，这时我们就有办法测量两座孤岛的距离；

但是，如果这两座孤岛之间无法相互联系，那么我们就无法测量这两座孤岛之间的距离，这时我们就可以将这个距离视为无穷（\infty），这就和钓鱼一样，钓不到的鱼一定是最大的。

四、连通

连通：连通指的是两个顶点之间存在路径。 非连通：非连通指的是两个顶点之间不存在路径。

graph LR
a---b
c

在上图中，顶点a和顶点b就是连通的，顶点c和其他两个顶点就是非连通的。

连通图：连通图指的是所有的顶点都是连通的无向图。

graph LR
a---b---c

在上图中，所有的顶点之间都存在路径，因此顶点与顶点之间都是连通的。像这种顶点与顶点之间都连通的无向图，我们就称为连通图。

非连通图：非连通图指的是存在非连通的顶点的无向图。

graph LR
a---b---c
d

在上图中，顶点d与其它顶点都不连通，像这种存在非连通的无向图，我们就称为非连通图。

强连通：强连通指的是两个顶点之间相互存在有向路径。 非强连通：非强连通指的是两个顶点之间最多存在一条有向路径。

graph LR
a-->b-->c
b-->a

在上图中，顶点a和顶点b之间既存在弧<a, b>，又存在弧<b, a>，因此我们称这两个顶点式强连通的；顶点b和顶点c之间只存在弧<b, c>，并不存在弧<c, b>，因此我们称这两个顶点是非强连通的。

强连通图：强连通图指的是所有顶点之间都是强连通的有向图。

graph LR
a-->b-->c-->b-->a

在上图中，顶点与顶点之间都是连通的，这就是我们说的强连通图。

非强连通图：非强连通图指的是存在非强连通顶点的有向图。

graph LR
a-->b-->c-->b-->a
c-->d
e

在上图中，顶点d和顶点e就是非强连通顶点：

• 顶点d与其它顶点之间只存在一条单向路径
• 顶点e与其它顶点之间不存在路径

像这种存在非强连通顶点的有向图就是非强连通图。

五、子图

子图：子图指的是图G的子集。

graph LR
a-->b-->c-->b-->a
c-->d
e

在这个有向图中，我们可以取一个子集：

graph LR
a-->b-->c-->d
e

这个子集就是原图G的子图。但是并不是任何子集都是原图的子图：

graph LR
a-->b-->c-->d[无顶点]
e

当我们所取的子集无法构成一个图时，那么这个子集就不是原图的子图。

生成子图：生成子图指的是由原图中的所有顶点集以及边集的子集构成的图。

graph LR
a
b-->c-->d
e

上图是我们在原图中所取的一个有顶点集和边集的子集构成的子图，这就是原图的一个生成子图。

在生成子图 G' 中，顶点集 V' 一定与原图的顶点集 V 相等，即 V' \iff V 。

极大连通子图：极大连通子图又称为连通分量，指的是在无向图子图中，包含尽可能多的顶点与边组成的子图，且该子图也是一个连通图。

graph LR
a---b---c
d

在这个无向图中，存在两个子图：

• 图 G_1 = (V_1, E_1), 其中 V_1 = {a, b, c},\ E_1 = {(a, b), (b, c)}

graph LR
a---b---c

• 图 G_2 = (V_2, E_2), 其中 V_2 = {d},\ E_1 = {\varnothing}

graph LR
d

这两个子图就是图G的两个连通分量。

这时有朋友可能就会问了，是不是所有的子图只要是连通图，那就是一个连通分量呢？

如子图 G_3 = (V_3, E_3), 其中 V_1 = {a, b},\ E_1 = {(a, b)}

graph LR
a---b

很遗憾的告诉你，这个子图不是连通分量。这里我们一定要谨记连通分量是图中极大的连通子图，即子图内的所有顶点必须相互连通，且无法通过添加更多的顶点或边来维持这种连通性。

像子图G_3我们就可以通过增加顶点c继续维持这种连通性，因此子图G_3不是图G的连通分量。

极大强连通子图：极大强连通子图又称为强连通分量，是有向图的子图中包含尽可能多的顶点和边组成的强连通图。

这里我就不再举例说明，我们只需要明确几点：

• 无向图中，顶点与顶点之间存在路径称为连通
• 有向图中，顶点与顶点之间相互存在有向路径称为强连通
• 极大连通子图是无向图中的连通分量
• 极大强连通子图是有向图中的强连通分量

结语

内容总结

本文系统讲解了图的五大核心概念：

1. 顶点的度：无向图的度直接计数，有向图区分入度、出度，并验证了全图入度与出度之和相等。
2. 路径与回路：通过无向图与有向图的对比，明确了简单路径、回路的定义及路径长度的计算。
3. 距离与连通性：距离是两顶点的最短路径长度，连通图（无向）与强连通图（有向）的判断标准得以清晰划分。
4. 子图与连通分量：生成子图需保留所有顶点，而连通分量是“不可扩展”的极大连通子图。

下期预告

下一篇中，我们将继续深入： • 生成树：连通图的极小连通子图 • 边的权：带权图的应用场景（如最短路径问题） • 稠密图与稀疏图：边数与顶点数的关系对算法效率的影响

互动提醒

如果本文对你有所启发，欢迎： • 点赞⭐收藏：方便随时回顾 • 评论