前面我们讲过的线性表（顺序表、链表、栈、队列）和树（二叉树、搜索树、平衡树）里，结点之间的关系要么是"一个接一个"（线性表），要么是"一个父节点带若干孩子"（树）。你有没有发现，这两种结构都有一个共同点：每个结点之间的关系相对简单、有固定的"形状"。线性表里，1 的前面只能有一个数、后面只能有一个数；树里，除了根，每个结点只有唯一的一个父亲。

那如果让你表示"任意两个结点之间都可能相连"的关系呢？比如一张社交网络里，谁和谁是好友；一张地图上，哪些城市之间有直达的高速公路；一个电路里，哪些元器件在物理上连着。这时候用线性和树都很别扭，因为你没法规定"谁必须是某个结点的唯一父亲"。图（Graph），就是专门为这种"多对多"关系而生的数据结构。

学习图的路线先给你画出来，心里有个地图，后面不容易迷路：先搞懂图长什么样（基本概念）→ 再想怎么存进计算机里（存储结构）→ 然后学会怎么把每个顶点都走一遍（遍历 BFS/DFS）→ 在有向无环图上排个先后顺序（拓扑排序）→ 最后研究两个经典考题：如何把 n 个点用权值和最小的边连通（最小生成树），以及如何找到两点之间权值和最小的路（最短路径）。这一路下来，你会发现图其实是一个"细节很多、但套路很固定"的领域，吃透它，你在很多涉及关系网络的题目里都能游刃有余。

图的基本概念

图的定义：G=(V,E)

图（Graph）由两部分组成：顶点集合 V 和边集合 E，记作 G = (V, E)。

  • 顶点集合 V：V = {x | x 属于某个数据对象集}，是一个有穷非空集合。顶点（vertex）就是图中的"结点"或"节点"，我们习惯把第 i 个顶点记作 vi。
  • 边集合 E：E = {(x,y) 或 <x,y> | x,y ∈ V 且存在边的关系}，是顶点之间关系的有穷集合，也叫边的集合。图中的第 k 条边记作 ek，它要么形如 ek=(vi,vj)，要么形如 ek=<vi,vj>——这一对括号的方向是理解有向图和无向图的关键，我们马上讲。

先记一个重点：图 = 顶点 + 边，顶点是"数据本身"，边是"数据之间的关系"，二者缺一不可。而我们后面讨论的所有存储和遍历算法，本质都是在处理这两样东西：怎么把"顶点"和"边"装进内存，怎么沿着"边"把"顶点"都走一遍。

顶点与边

顶点就是图中的结点，这个好理解。边就是连接两个顶点的一条"线"，表示这两个顶点之间存在某种关系。比如社交网络里，张三和李四是好友，那"张三——李四"就是一条边；地图上北京和天津之间有条高速，那"北京——天津"就是一条边。

以下几个概念需要区分清楚：

  • 两个顶点 vi 和 vj 相关联，指的就是 vi 和 vj 之间有一条边，也就是它们"挨着"。
  • 如果 vi 和 vj 之间有一条边，就称 vi 和 vj 是直接相关的，或者说这条边"依附于"这两个顶点。

有向图和无向图

这是图最重要的一个分类，它的本质区别在于边到底有没有方向。

无向图：边用圆括号 (x, y) 表示。(x, y) 表示 x 到 y 的一条双向通路，也就是说无向边没有方向。(x, y) 和 (y, x) 是同一条边——从 x 能到 y，从 y 也一定能到 x。

画成图大概是这样的（用 G1 表示顶点集合 {v0,v1,v2} 的无向图）：

无向图 G1（三条边连接三个顶点，完全图）
     v0
    /  \
   v1——v2
边为 (v0,v1)、(v0,v2)、(v1,v2)

有向图：边用尖括号 <x, y> 表示。<x, y> 表示从 x 到 y 的一条单向通路（也叫弧，x 是弧尾，y 是弧头）。在有向图中，<x, y> 和 <y, x> 是两条不同的边。

有向图 G4（四条边，方向各不相同）
     v0 ——> v1
     ^       |
     |       v
     v3 <—— v2
边为 <v0,v1>、<v1,v2>、<v2,v3>、<v3,v0>

这里有个关键的小结，课件里特别强调，将来做题也常考：无向边 (x, y) 等价于两条有向边 <x, y> 和 <y, x>。也就是说，你可以把一条无向边"拆"成方向相反的两条有向边来理解。这事非常重要，后面你写邻接矩阵和邻接表时，同样一条无向边要"写两遍"，靠的就是这个思想。

完全图

完全图指的是边数达到"上限"的图，再也不能多加一条边了：

  • 无向完全图：有 n 个顶点，若有 n*(n-1)/2 条边，即任意两个顶点之间有且仅有一条边，就称其为无向完全图。为什么是 n*(n-1)/2？因为 n 个顶点两两组合的个数是 C(n,2) = n*(n-1)/2。上面那个 G1 就是 3 个顶点的无向完全图，有 3*2/2 = 3 条边。
  • 有向完全图：有 n 个顶点，若有 n*(n-1) 条边，即任意两个顶点之间有且仅有方向相反的边（既有 <x,y> 又有 <y,x>），就称其为有向完全图。上面那个 G4 就是 4 个顶点的有向完全图，有 4*3 = 12 条边。

这个"完全图的边数公式"常用来判断一个图是不是"满的"，也常在考题里出现，建议记住。

邻接顶点

邻接顶点（也叫相邻顶点、邻接点）：两个顶点之间直接连着一条边，互为邻接。

  • 在无向图 G 中，若 (u, v) 是 E(G) 的一条边，就称 u 和 v 互为邻接顶点，并称边 (u,v) 依附于顶点 u 和顶点 v。
  • 在有向图 G 中，若 <u, v> 是 E(G) 的一条边，则称 顶点 u 邻接到 v，顶点 v 邻接自顶点 u，并称边 <u, v> 与顶点 u、v 相关联。注意这里"邻接到"与"邻接自"的方向是反过来的：u 是起点（邻接到 v），v 是终点（被邻接，即邻接自 u）。

这里的有向邻接方向，和后面"出度/入度"、"出度表"都是一一对应的，务必分清"谁邻接到谁"。

顶点的度：入度与出度

度（degree）：顶点 v 的度是指与它相关联的边的条数，记作 deg(v)。度从一个侧面反映了这个顶点在图里有多"忙"——边越多，度越大。

在无向图中，顶点的度等于与它相连的边的条数。一条边连着两个顶点，所以无向图中所有顶点的度之和等于边数的两倍（2*|E|），因为每条边被数了两次。

在有向图中，度要分成两类，因为边有方向：

  • 入度（in-degree）indeg(v)：以 v 为终点的有向边（指向 v 的边）的条数，记作 indeg(v)，课件里写作 indev(v)（一个拼写笔误，意即入度）。
  • 出度（out-degree）outdeg(v)：以 v 为起点的有向边（从 v 出发的边）的条数，记作 outdeg(v)，课件写作 outdev(v)。

于是有向图中顶点的度等于入度与出度之和：dev(v) = indev(v) + outdev(v)（课件里 dev 即 deg 的笔误）。

但注意课件里有一句容易误导的话："对于无向图，顶点的度等于该顶点的入度和出度，即 dev(v) = indev(v) = outdev(v)。"这句话我给你的通顺理解是：无向图的边没有方向，所以无需区分入度和出度，它的度就是边的条数本身。如果你强行在无向图里硬套"入度=出度"这个说法，它只在"无向边等价于两条反向有向边"这种等价意义下成立，并非真的有入度和出度这回事。所以请你脑子里记清楚：

  • 无向图：deg(v) = 与 v 相连的边数，不分入出。
  • 有向图：deg(v) = indeg(v) + outdeg(v)。

有向图还有个漂亮的性质，将来你能用它自查：所有顶点的入度之和 = 所有顶点的出度之和 = 有向边总数，因为每条有向边给起点贡献 1 个出度、给终点贡献 1 个入度，两边刚好各自都数了一次。

路径、路径长度、简单路径与回路

路径：在图 G=(V,E) 中，若从顶点 vi 出发，有一组边能使其到达顶点 vj，则称从 vi 到 vj 的这个顶点序列为从 vi 到 vj 的路径。通俗说，就是"从 A 到 B，走哪几条边、路过哪些城市的线路"。

路径长度：

  • 对于不带权的图（边只有"有"或"没有"，没有数值），一条路径的路径长度是指该路径上边的条数。路径上有几条边，长度就是几。相当于"走了几步"。
  • 对于带权的图（每条边带一个数值，比如距离），一条路径的路径长度是指该路径上各个边权值的总和。相当于"走的这几步一共花了多少路程/时间/费用"。

简单路径与回路：

  • 简单路径：若路径上各个顶点 v1,v2,v3,…,vm 均不重复（不回头走同一个点），则称其为简单路径。
  • 回路/环（cycle）：若一条路径上第一个顶点 v1 和最后一个顶点 vm 重合（走了一圈回到起点，而中间的其他顶点互不相同），则称这条路径为回路或环。

简单路径和回路的直觉：简单路径是"不重复走点"的路径，回路是"转了一圈又回来"的闭合路径。这里要特别注意一个约定：我们讨论的最短路径、以及用 DFS 遍历时，默认只在简单路径 / 无环的前提下才有明确意义。因为如果存在负权回路（后面 Dijkstra 一节会专门讲），最短路径甚至可能不存在（可以无限绕圈越绕越短）。

子图

子图：设图 G = (V, E) 和图 G1 = (V1, E1)，若 V1 ⊆ V 且 E1 ⊆ E，则称 G1 是 G 的子图。

子图很好理解：子图的顶点是从原图的顶点里挑一部分，子图的边是从原图的边里挑一部分，而且要保证挑出来的边两边端点都在挑出来的顶点里（这是隐含约定，否则边会悬空）。子图概念在后面"连通分量"、"生成树"里都会用到。

连通图、连通分量与强连通图

这几个概念非常容易混，我拆开讲清楚。

连通（connected）：在无向图中，若从顶点 v1 到顶点 v2 有路径（不管多长、中间路过几个点），则称 v1 与 v2 是连通的。注意是"有路径"就行，不需要直接相连。

连通图：在无向图中，若图中任意一对顶点都是连通的，则称此图为连通图。也就是"随便找两个点，都走得通"。

连通分量（connected component）：一个无向图的极大连通子图称为这个图的一个连通分量。这里"极大"的意思是不能扩大——已经把能连通的顶点和连接它们的边都尽量包进来了，再加任何顶点或边就会脱离连通。一个连通图只有一个连通分量，就是它自己；一个不连通的无向图会被分成若干个连通分量，就像一堆分散的岛屿，每个岛屿是一个连通分量。记住：连通分量映射到程序中，就是"这个图被分成了几块互不连通的大岛"，遍历时你就需要好几个起点才能走遍所有点。

强连通图：这个针对有向图。在有向图中，若在每一对顶点 vi 和 vj 之间，既存在一条从 vi 到 vj 的路径，也存在一条从 vj 到 vi 的路径，则称此有向图是强连通图。因为有向边有方向，仅从一个方向走得通不算强连通，必须两个方向都通。

强连通分量（SCC, Strongly Connected Component）：有向图的极大强连通子图。这个概念通常在求 SCC 的 Tarjan / Kosaraju 算法里用得多，课件框架下我们只要求知道"强连通"的定义即可，但提一嘴方便你留个印象。

给你的对比口诀：无向图用"连通"，连通图只有一个连通分量；有向图才谈"强连通"，讲究来回都能通。

生成树

生成树：一个连通图的最小连通子图称作该图的生成树。关键性质：有 n 个顶点的连通图，其生成树有 n 个顶点和 n-1 条边，且是连通的、无回路的。

"最小连通子图"是我上面反复强调的"极大"的镜像：在保持所有 n 个顶点连通的前提下，边数最少、且不能有环。为什么是 n-1 条边？因为把 n 个点连通的最少边数恰好是 n-1（所有点连成一条不闭合的链，或者连成一棵树形结构），多一条就会成环，少一条就有点孤岛。而"树"这个词在这里的意思就是"无环连通图"。生成树是后面最小生成树（MST）的铺垫——最小生成树就是在所有可能的生成树里，让边的权值总和最小的那一棵。

顺便记一个要点：一个连通图的生成树不唯一（有很多种连法都能连通 n 个点），但边数固定是 n-1。最小生成树就是从中挑权值和最小的一棵。

概念部分先讲到这里，内容多但都是"骨肉"级的。接下来进入正式的动手环节——先解决"图怎么存进计算机"。这是算法的地基，存法直接决定后面每个算法怎么写、有多快。

图的存储结构

图的存储本质上只关心两件事：顶点集合和边集合（顶点间的两两关系）。顶点比较简单，用一个连续数组存起来就行（比如用 vector<V> _vertexs）；难的是边，因为它是"两两之间"的关系。业界有两套主流存法：邻接矩阵和邻接表。它们的取舍一句话概括：邻接矩阵擅长稠密图（边很多）、查询两点是否相邻快、但费空间；邻接表擅长稀疏图（边很少）、省空间、但查询某个邻居要沿着链表走。下面拆开讲。

邻接矩阵（稠密图的存储）

邻接矩阵的思路是：用一个**二维数组（矩阵）**来表示顶点之间的关系。matrix[i][j] 的值表示顶点 i 和顶点 j 之间是否有边（或者说边的权值是多少）。

  • 先用一个一维数组把顶点存起来（_vertexs，建立"顶点的名字/数据 → 下标 i"的映射 _vIndexMap）。
  • 再用一个 n×n 的二维矩阵来表示关系：matrix[i][j] != 无 表示顶点 i 到顶点 j 有边。

画个简单的无向图及其邻接矩阵给你看，顶点 {v0,v1,v2}，三条边 (v0,v1)、(v0,v2)、(v1,v2)：

无向图：             邻接矩阵（v0,v1,v2 下标依次为 0,1,2）
  v0                  <----- 无向图矩阵是对称的
 /  \                    v0  v1  v2
v1——v2                 v0  0   1   1
                       v1  1   0   1
                       v2  1   1   0

课件里讲的用邻接矩阵存储的注意点，这里帮你把每一条都讲透：

  1. 无向图的邻接矩阵是对称的，因为 (i,j) 和 (j,i) 是同一条无向边，matrix[i][j] == matrix[j][i]。并且，第 i 行（或第 i 列）的元素之和，就是顶点 i 的度。因为第 i 行每一列的非零项都代表一条连接 i 的边，加起来就是 i 的关联边数。
  2. 有向图的邻接矩阵不一定对称。有向图中，第 i 行（matrix[i][*]）元素之和是顶点 i 的出度（因为行代表"从 i 出发指向谁"），第 i 列（matrix[*][i]）元素之和是顶点 i 的入度（因为列代表"谁指向 i"）。这是行/列与出/入度的一一对应，常考。
  3. 如果边带权值，两个连通顶点的位置就存权值代替"1"；两个不连通的顶点则存无穷大（∞）代替"0"。为什么用无穷大而不用 0？因为这给你一个天然的边界判定：matrix[i][j] == ∞ 说明 i 到 j 没有路，而 dist[u] + matrix[u][k] 这类求和时，∞ 参与会"撑爆"中间结果从而被正确排除。用一个很大的数（如 INT_MAX）当"不可能到达"的哨兵，是后面最短路径算法的关键约定。

用邻接矩阵存储的优点：能够快速（O(1)）知道两个顶点是否连通——直接看 matrix[i][j] 是不是无穷大即可。

用邻接矩阵存储的缺点：

  • 如果顶点比较多、边比较少，矩阵里存了大量"无穷大/0"，这类矩阵叫稀疏矩阵，很浪费空间（需要 O(n²) 空间，而边可能只有 O(n) 条）。
  • 想枚举一个顶点的所有邻居，得把整行 O(n) 个元素都扫一遍，慢。
  • 课件还提到一句"要求两个节点之间的路径不是很好求"——意思是只用矩阵本身并不直观，求路径往往要配合别的算法显式去算。

邻接表（稀疏图的存储）

邻接表的思路：用数组表示顶点的集合，用链表表示边的关系。每个顶点对应一条链表，链表的结点就是这个顶点直接能到达的邻居（以及对应边的权值）。

  • _linkTable[i] 是以顶点 i 为尾的边的链表头指针，链表中每个结点存一个邻居（_dstIndex）和权值（_w）。

画一个无向图和有向图的邻接表给你看，顶点 {v0,v1,v2}，无向图三条边 (v0,v1)、(v0,v2)、(v1,v2)，有向图三条有向边 <v0,v1>、<v0,v2>、<v1,v2>：

无向图邻接表：
_vertexs    边链表
  v0  -->   [v1] --> [v2] --> NULL
  v1  -->   [v0] --> [v2] --> NULL
  v2  -->   [v0] --> [v1] --> NULL

有向图邻接表（只存"从某点出发能到哪"）：
_vertexs    出度表
  v0  -->   [v1] --> [v2] --> NULL
  v1  -->   [v2] --> NULL
  v2  -->   NULL（v2 没有出边）

邻接表存储的注意点（课件强调两处）：

  1. 无向图中，同一条边在邻接表里出现了两次（v0 的链表里有 v1，v1 的链表里也有 v0）。想要知道顶点 vi 的度，只需求出 vi 的边链表中的结点个数即可。
  2. 有向图中，每条有向边在邻接表里只出现一次。与顶点 vi 对应的邻接表所含结点的个数，就是该顶点的出度，所以有向图的邻接表也叫出度表（存的是"我从哪出发"）。如果要得到 vi 的入度，必须去检测其他所有顶点对应的边链表，数一数有多少个结点的 _dstIndex == i。

有向图邻接表的缺点与补救：出度表算入度很麻烦（要扫所有顶点）。如果想高效地同时支持「求入度快」和「求出度快」，业界常引入逆邻接表（入度表，存"谁能到我"）。实际工程里（比如拓扑排序）常直接用入度数组统计每个顶点的入度，不必建两张表。

邻接矩阵 vs 邻接表：到底怎么选

这是图里最常考的一道"选择题"，我帮你把决策标准固定下来：

对比项邻接矩阵邻接表
空间固定 O(n²)，稠密图划算O(n+e)，e 是边数，稀疏图划算
判断两点是否相邻O(1)，直接查矩阵O(度)，要沿链表找
枚举某顶点的邻居O(n)，要扫一整行O(度)，只走链表
适用场景稠密图（边数接近完全图）、需要快速判连通稀疏图（边远少于完全图）、需要省空间

一句话决策准则：稠密图用邻接矩阵，稀疏图用邻接表；疯狂要"查两点是否相邻"用矩阵，要"逐条枚举所有边 / 省空间"用表。 判断稠密还是稀疏的参考线：当边数 e 远大于 n（接近 n²/2）算稠密，e 接近 n 或更小算稀疏。

下面给出一个基于模板 + 邻接矩阵的完整可编译的 Graph 类，它把顶点数组、顶点↔下标映射、矩阵、加边、打印都实现了。这个类也是后面讲遍历、最短路径时反复复用的"骨架"。为了让你直接能跑，我把类定义和测试代码拼成完整程序：

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <climits>      // INT_MAX
#include <stdexcept>    // invalid_argument
using namespace std;
 
// W 是权值类型，MAX_W 用作"两点不连通"的哨兵值，Direction 表示是否是有向图
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
    typedef Graph<V, W, MAX_W, Direction> Self;
 
    Graph() = default;
 
    // 用顶点数组 vertexs 构造：初始化顶点集合、顶点->下标映射，并把矩阵全部填成 MAX_W
    Graph(const V* vertexs, size_t n)
    {
        _vertexs.reserve(n);
        for (size_t i = 0; i < n; ++i)
        {
            _vertexs.push_back(vertexs[i]);   // 存顶点
            _vIndexMap[vertexs[i]] = i;       // 建立 顶点->下标 映射
        }
        // MAX_W 作为"无边"的标识值
        _matrix.resize(n);
        for (auto& e : _matrix)
            e.resize(n, MAX_W);               // 矩阵全部初始化为"不连通"
    }
 
    // 根据顶点数据 v 找到它的下标；找不到就抛异常
    size_t GetVertexIndex(const V& v)
    {
        auto ret = _vIndexMap.find(v);
        if (ret != _vIndexMap.end())
            return ret->second;
        throw invalid_argument("顶点不存在");
    }
 
    // 内部加边：已知两个下标 srci、dsti，填矩阵；无向图要把对称位置也填上
    void _AddEdge(size_t srci, size_t dsti, const W& w)
    {
        _matrix[srci][dsti] = w;              // 有向边 <srci,dsti> 的权值
        if (Direction == false)               // 无向图要补对称边
            _matrix[dsti][srci] = w;
    }
 
    // 对外加边：先查下标，再调用 _AddEdge
    void AddEdge(const V& src, const V& dst, const W& w)
    {
        size_t srci = GetVertexIndex(src);
        size_t dsti = GetVertexIndex(dst);
        _AddEdge(srci, dsti, w);
    }
 
    // 打印邻接矩阵和所有边，方便观察
    void Print()
    {
        // 打印顶点和下标映射关系
        cout << "顶点映射: ";
        for (size_t i = 0; i < _vertexs.size(); ++i)
            cout << _vertexs[i] << "-" << i << " ";
        cout << endl << endl;
 
        cout << "邻接矩阵:" << endl;
        // 打印列坐标提示
        cout << "  ";
        for (size_t i = 0; i < _vertexs.size(); ++i)
            cout << i << " ";
        cout << endl;
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            cout << i << " ";
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (_matrix[i][j] != MAX_W)
                    cout << _matrix[i][j] << " ";
                else
                    cout << "#" << " ";       // # 表示无边
            }
            cout << endl;
        }
        cout << endl;
 
        // 打印所有边（i<j 避免无向图的对称边重复打印）
        cout << "所有边:" << endl;
        for (size_t i = 0; i < _matrix.size(); ++i)
            for (size_t j = 0; j < _matrix[i].size(); ++j)
                if (i < j && _matrix[i][j] != MAX_W)
                    cout << _vertexs[i] << "-" << _vertexs[j]
                         << ":" << _matrix[i][j] << endl;
    }
 
private:
    map<V, size_t> _vIndexMap;    // 顶点数据 -> 下标 的映射
    vector<V> _vertexs;           // 顶点集合
    vector<vector<W>> _matrix;    // 存边的邻接矩阵
};
 
int main()
{
    // 有向图测试：顶点 0,1,2,3，权值如课件所示
    Graph<char, int, INT_MAX, true> g("0123", 4);
    g.AddEdge('0', '1', 1);
    g.AddEdge('0', '3', 4);
    g.AddEdge('1', '3', 2);
    g.AddEdge('1', '2', 9);
    g.AddEdge('2', '3', 8);
    g.AddEdge('2', '1', 5);
    g.AddEdge('2', '0', 3);
    g.AddEdge('3', '2', 6);
    g.Print();
    return 0;
}

这个类的设计里有三个值得品的细节：

  1. GetVertexIndex 用 map 建映射：顶点作为"数据"（可能是字符串、字符、甚至结构体）不能用下标直接访问，所以用一个 map<V,size_t> 把它映射到 0..n-1 的下标。这也是"先定位下标，再操作矩阵"的统一入口。
  2. _AddEdge 与 AddEdge 分成两层：内部层直接收下标（知道下标了），外部层收顶点数据（要先查下标）。这种分层让后面最小生成树等算法能直接用下标高效加边。
  3. Direction 模板参数控制对称性：加边时 if (Direction == false) 才回填对称位置，一份代码同时支持有向图与无向图。

编译运行这段程序，你会看到矩阵里 # 表示无边、数字表示有权边，以及所有非对称打印出来的边，非常直观。

图的遍历：BFS 与 DFS

遍历的定义：给定一个图 G 和其中任意一个顶点 v0，从 v0 出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。"遍历"即对每个结点进行某种操作（比如打印、修改）的意思。

先把课件里那个很棒的思考题摆出来，再回答它：

思考：树以前是怎么遍历的？此处可以直接用树的遍历方式来遍历图吗？为什么？

答案：树的遍历（前序、中序、后序、层序）不能直接照搬到图上，原因有二：

  • 树没有回路，图有回路。树的遍历天然不会走回已经走过的结点（每个结点只有唯一父亲，天然单向无环）；但图可能有环（回路），走进去可能"绕着圈回不到头"，所以必须显式地标记"哪些顶点已经访问过"（visited），否则会死循环。
  • 图的起点不一定能到达所有顶点。一棵树从根出发能到达所有结点；但非连通图从某个顶点出发，只能走到它所在的连通分量，其他"岛屿"永远走不到。所以遍历完还不够，还得从所有"还没访问过"的顶点分别出发再补遍（下一节会看到这个套路）。

因此，图的遍历必须围绕两个"防坑点"设计：①用 visited 数组防止重复访问（防死循环）；②遍历结束后，还要循环找出所有没访问过的顶点再各来一遍（覆盖多个连通分量）。这两个点在下面的 BFS、DFS 里都会出现。

图的广度优先遍历（BFS）

BFS（Breadth First Search，广度优先搜索）：从起点出发，一层一层地向外扩散访问顶点——先访问起点的所有直接邻居，再访问这些邻居的所有邻居（跳过已访问的），以此类推。就像往水里扔一颗石子，波纹一圈圈往外荡。

BFS 的核心数据结构是队列（queue）——先进先出，天然符合"先到的先扩散"。

画个无向图观察 BFS 扩层，顶点 {v0,v1,v2,v3,v4}，边 (v0,v1)、(v0,v2)、(v1,v3)、(v2,v4)；从 v0 出发：

队列演进（从 v0 出发，箭头后是每次弹出一个节点并放入它的未访问邻居）：
 v0 进队:           队列 [v0]
 弹 v0, 入 v1 v2:   队列 [v1, v2]     （第1层）
 弹 v1, 入 v3:      队列 [v2, v3]
 弹 v2, 入 v4:      队列 [v3, v4]     （v0已访问跳过）
 弹 v3:            队列 [v4]
 弹 v4:            队列 []
依次访问: v0 v1 v2 v3 v4   ->  这就是 BFS 的层序

实现时还要处理一件重要的事：同一个顶点可能被多个顶点同时"想"入队（比如两个邻居都想把它加进来），所以要在入队那一刻就标记 visited，而不是出队时才标记。否则一个顶点可能被重复放入队列多次，造成重复访问甚至死循环。这是 BFS 最容易写错的地方，我在代码里特意标注。

下面基于邻接矩阵的 Graph 类给出 BFS 完整实现（直接用我们上面建好的类，加一个成员函数）：

// ---- 加到 Graph 类里的 BFS ----
void BFS(const V& src)
{
    size_t srci = GetVertexIndex(src);   // 源顶点的下标
    vector<bool> visited(_vertexs.size(), false); // 访问标记数组，全 false
    queue<size_t> q;                     // 队列，存顶点下标
    q.push(srci);                        // 起点入队
    visited[srci] = true;                // 入队即标记，防止重复入队
 
    size_t level = 0;                    // 记录当前是第几层（可选）
    while (!q.empty())
    {
        size_t levelSize = q.size();     // 当前层的顶点数
        cout << "第" << level << "层: ";
        for (size_t k = 0; k < levelSize; ++k)  // 一次处理完一层
        {
            size_t front = q.front();
            q.pop();
            cout << _vertexs[front] << " ";     // 访问当前顶点
            // 扫描整行，把与 front 有边且未访问的邻居入队
            for (size_t i = 0; i < _vertexs.size(); ++i)
            {
                if (_matrix[front][i] != MAX_W && visited[i] == false)
                {
                    visited[i] = true;          // 入队前必须标记！
                    q.push(i);
                }
            }
        }
        cout << endl;
        ++level;
    }
}

BFS 的骨架要点：

  • visited[srci] = true 在入队时紧跟执行；每次要把邻居入队前，先检查 visited[i] == false，一入队立刻 visited[i] = true。这样保证每个顶点只入队一次。
  • 外面那层 while(!q.empty()) 配合 levelSize 实现"按层"访问，方便你观察层序（比如求"离起点第 K 层有哪些点"）。如果只关心"访问顺序"，可以把内层的 levelSize 那层 for 简化掉，直接每弹一个就入队一批。
  • 在矩阵实现下，找邻居要扫一整行 O(n)，所以矩阵版 BFS 总复杂度 O(n²)。

图的深度优先遍历（DFS）

DFS（Depth First Search，深度优先搜索）：从起点出发，沿着一条路走到黑，走不动了再回退（回溯）到最近的分岔口，换一条路继续走，直到把能到的顶点都走完。就像走迷宫"一条道走到死，撞墙就退回来换一条"。

DFS 的思想可以用递归来表达（递归天然就是"深入到不能再深再回溯"），也可以用显式栈表达（本质就是模拟递归）。下面是递归版，递归天然契合"深入再返回"的逻辑。

课件里给的递归框架是这样的：_DFS 递归函数，传入当前下标和 visited 引用，访问后递归所有邻居。但这里有个容易踩的坑：递归里对已访问的判断最好在"进函数时"就做（if(!visited[index])），而不是在"递归子调用前"做，否则会多一层没意义的递归栈。两种都对，但前一种更省事。我给一个清晰版本：

// ---- 加到 Graph 类里的 DFS ----
// 递归辅助函数：从下标 index 出发深度优先访问，visited 引用共享
void _DFS(size_t index, vector<bool>& visited)
{
    if (visited[index])      // 已经访问过就返回（防环）
        return;
    cout << _vertexs[index] << " ";  // 访问当前顶点
    visited[index] = true;           // 标记已访问
    // 沿着 index 能到的所有未访问邻居继续深挖
    for (size_t i = 0; i < _vertexs.size(); ++i)
    {
        if (_matrix[index][i] != MAX_W && visited[i] == false)
            _DFS(i, visited);        // 递归进入邻居（深度优先）
    }
}
 
// 对外接口：从 v 出发做 DFS；v 所在的连通分量遍历完后，再把其余没访问过的顶点也各自 DFS 一遍
void DFS(const V& v)
{
    cout << "DFS: ";
    size_t srci = GetVertexIndex(v);
    vector<bool> visited(_vertexs.size(), false);
    _DFS(srci, visited);                       // 先深挖起点所在分量
    // 处理非连通图：把其余没访问的每个顶点都作为起点再来一轮 DFS
    for (size_t i = 0; i < _vertexs.size(); ++i)
        if (visited[i] == false)
            _DFS(i, visited);
    cout << endl;
}

DFS 里最有价值的一点，是那个对非连通图的兜底循环：for (size_t i...) if(!visited[i]) _DFS(i, visited)。它保证了即便起点无法到达某些顶点，也能把整张图都遍历完。这一小步，本质就是在"按连通分量划分图，逐个分量做 DFS"——前面概念里的"连通分量"在这儿派上了用场。

递归用栈尾的风险：DFS 递归在最坏情况下（图退化成一条长长的链，或深度很大的图）可能调用栈非常深。如果图很大，可以改写成显式栈的迭代版本以避免栈溢出。这里给一个迭代版，用的是 stack 后进先出：

// 迭代版 DFS：用显式栈模拟递归的"深入到最深"，含非连通图兜底
void DFS_Iterative()
{
    vector<bool> visited(_vertexs.size(), false);
    for (size_t s = 0; s < _vertexs.size(); ++s)
    {
        if (visited[s]) continue;          // 跳过已访问分量
        stack<size_t> st;
        st.push(s);
        while (!st.empty())
        {
            size_t top = st.top();
            st.pop();
            if (visited[top]) continue;    // 已访问则跳过（因为可能被重复入栈）
            visited[top] = true;           // 出栈时标记
            cout << _vertexs[top] << " ";
            // 把所有未访问邻居入栈（后进先出，先入的后处理）
            for (size_t i = 0; i < _vertexs.size(); ++i)
                if (_matrix[top][i] != MAX_W && visited[i] == false)
                    st.push(i);
        }
    }
}

注意迭代 DFS 标记 visited 的时机和 BFS 不同：BFS 是"入队即标"，迭代 DFS 这里是"出栈才标"。出栈才标会让同一个顶点可能被多次 push 进栈（重复但无害，出栈时 if(visited[top]) continue 会拦掉重复），换来的是递归语义的等价。两种写法都能跑，笔试时用简洁的递归版即可，心里知道有栈溢出风险、能换成迭代版就好。

遍历总结：BFS 用队列、一层层扩散，适合"求最短跳数/层数"；DFS 用递归或栈、一条条深挖，适合"探索所有可能路径/检测连通性"。二者的共同地基是 visited 数组 + 对非连通图的兜底循环，这两个是图遍历的"灵魂"，请务必记牢。

补充：连通分量与遍历的实战关联

上面反复提到"非连通图的兜底循环"，这里把"连通分量"和遍历彻底绑定一下，你会觉得恰到好处：

  • 一个无向图有 k 个连通分量，那么你用同一个 DFS/BFS 函数从任意点出发，需要启动 k 次（每次在没访问过的新顶点开跑）才能走完所有顶点。连通分量个数 = DFS/BFS 启动次数（去掉第一次）。这是个很实用的技巧：经常用来判断"图是否连通"（启动次数是否为 1）。
  • 所以在实现通用的图遍历时，永远要保留那层"遍历完√ 起点分量后再补一遍其它未访问顶点"的循环，否则你写的遍历只对连通图成立。

拓扑排序：给有向无环图排先后

拓扑排序（Topological Sort）是图（专指有向无环图 DAG）里一个高频概念，值得大书特书。先给定义，再讲意义和算法。

拓扑序（topological order）：针对一个有向无环图，把它的所有顶点排成一个线性序列，使得如果存在有向边 <u,v>（u 指向 v，即 u 必须先于 v），那么在这个序列中 u 一定排在 v 的前面。得到的这个序列就叫拓扑序列/拓扑序。

拓扑排序的直觉：很多现实问题都是"某些事情必须先于另一些事情"，这是典型的先后依赖关系。比如课程安排（学完《高等数学》才能学《线性代数》）、项目任务调度（A 工程必须等 B 工程完成才能开始）、编译程序的依赖解析。把这种"先后依赖"画成有向图（A 指向 B 表示 A 必须先做），再排出一个合法的执行顺序，就是拓扑排序要做的事。

两个关键边界必须讲透：

  1. 只有有向无环图（DAG）才有拓扑序。 如果图里有环（比如 <A,B>、<B,C>、<C,A>），那 A 必须排在 B 前、B 必须排在 C 前、C 又必须排在 A 前——三者互相矛盾，根本排不出来，这是一个逻辑悖论。所以拓扑排序天然地承担了"检测有向图是否有环"的功能：如果能排出完整拓扑序，说明无环；排不满，说明一定有环。

  2. 拓扑序通常不唯一。 只要不破坏"u 必须在 v 前"的约束，同一个 DAG 常常能排出多种合法顺序。

Kahn 算法（基于入度的拓扑排序）

实现拓扑排序最经典的是 Kahn 算法，核心思路极其直观：

在一个 DAG 里，入度为 0 的顶点是"没有任何前置依赖"的顶点，可以直接"先做"。把它拿出来输出，同时"删掉"它（连带删掉从它出发的所有边），这样它指向的那些顶点的入度就会减少。重复这个过程：不断找出当前入度为 0 的顶点输出，直到所有顶点都输出完——这就是拓扑序。

用队列实现 Kahn 算法，代码（这里用一个独立的、基于邻接表的 DAG 类，独立可编译）：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
 
// 不带权重的有向图（邻接表，用于拓扑排序）
class Digraph
{
public:
    Digraph(int n) : _adj(n), _n(n) {}
 
    // 加一条有向边 u -> v（指向 v）
    void addEdge(int u, int v)
    {
        _adj[u].push_back(v);   // v 是 u 的邻居（u 指向 v）
    }
 
    // Kahn 拓扑排序：成功返回拓扑序列，若存在环则返回空 vector
    vector<int> topoSort()
    {
        vector<int> indeg(_n, 0);        // 每个顶点的入度
        for (int u = 0; u < _n; ++u)     // 统计所有边的入度
            for (int v : _adj[u])
                ++indeg[v];              // 边 u->v 使 v 的入度 +1
 
        queue<int> q;
        for (int i = 0; i < _n; ++i)
            if (indeg[i] == 0)           // 入度为 0 的顶点先入队（无前置依赖）
                q.push(i);
 
        vector<int> order;               // 收集拓扑序列
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            order.push_back(u);          // 输出当前可做的顶点
            for (int v : _adj[u])        // 删掉 u 的所有出边
                if (--indeg[v] == 0)     // 对应下游顶点入度减一，减到 0 就也能做了
                    q.push(v);
        }
        // 若排出的数量 != 顶点总数，说明存在环，无法完成拓扑排序
        if (order.size() != static_cast<size_t>(_n))
            return vector<int>();        // 有环，返回空表示失败
        return order;
    }
 
private:
    vector<list<int>> _adj;   // 邻接表
    int _n;                   // 顶点数
};
 
int main()
{
    // 一个合法 DAG：0->1, 0->2, 1->3, 2->3
    Digraph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
 
    vector<int> order = g.topoSort();
    if (order.empty())
        cout << "存在环，无法拓扑排序" << endl;
    else
    {
        cout << "拓扑序列: ";
        for (int x : order) cout << x << " ";
        cout << endl;
    }
    return 0;
}

Kahn 算法的正确性直观可证：每当入度为 0 的顶点被输出，它的所有前置依赖都已经处理完，所以可以"放心执行"；而它执行完又解除了对它下游顶点的依赖，于是下游顶点可能变成新的入度 0。反复迭代，DAG 就被一层层地"剥"成拓扑序了。

复杂度：邻接表实现下，统计入度 O(e)、队列操作 O(n+e)，总体 O(n+e)。

边界与坑：

  • 入度计算要准确，不能漏统计任何一条边，否则会"误判"出多余的入度 0 顶点。代码里统计入度时 ++indeg[v] 对应的是 u->v 这条边让 v 入度 +1，别写成 ++indeg[u]（那是出度）。
  • 输出顺序不唯一是正常现象，只要满足"u 在 v 前"约束就算正确。
  • 检测环的下限：只要最终排出的顶点数少于 n，就一定有环。这也常用来回答"这个任务编排有没有死锁/循环依赖"的问题。

把 DFS 和拓扑排序串一句：DFS 也能做拓扑排序（利用"回退到某顶点时它是在所有子孙之后访问的"这一性质，逆序收集），但 Kahn 算法基于入度、用队列，理解起来更直白，也是面试中更常用的写法，这里重点讲它。课件里拓扑排序没有显式列节，但它确实是图遍历的自然延伸，也是 BAT 笔试的高频题，我把它补进来很有必要。

最短路径问题

最短路径问题：从带权图（通常是有向图）中的某一顶点出发，找出一条通往另一顶点的最短路径，"最短"是指沿路径各边的权值总和最小。

这个问题按"起点个数"分成两类，我们逐一攻破：

  • 单源最短路径：给一个源点 s，求 s 到图中每个顶点的最短路径。代表作：Dijkstra（权值非负）、Bellman-Ford（允许负权、还能检测负环）。
  • 多源最短路径：求图中任意两点之间的最短路径。代表作：Floyd-Warshall（本质是动态规划）。

单源最短路径：Dijkstra 算法

Dijkstra（迪杰斯特拉）算法解决的是带权有向图（且边的权重非负）的单源最短路径问题。给定源点 s，它能求出 s 到每个顶点的最短路径。

它看起来很像贪心，确实是贪心算法。 下面用课件那套经典的"集合 S 与集合 Q"的语言讲清楚：

  • 把所有顶点分成两组：S（已经确定了最短路径的顶点集合）和 Q（其余尚未确定最短路径的顶点集合）。初始化时，S 至少放源点 s（因为 s 到自己的最短距离是 0），Q 是其余顶点。
  • 每次都从 Q 中找出一个"当前起点 s 到它代价最小"的顶点 u（贪心：这个 u 现在累的代价最小，优先"确定为最短"），把 u 从 Q 移入 S。
  • 对 u 的每一个相邻顶点 v 做松弛（relaxation）。

这里讲透"松弛"这个术语：松弛是求最短路径的核心操作。对于每条边 <u,v>，我们检查"经过 u 再到 v"是否比"原来到 v 的路径"更短：

如果 dist[s到u] + 边权<u,v>  <  当前 dist[s到v]
那么就把 dist[s到v] 更新为 dist[s到u] + 边权<u,v>，并把 v 的父亲记成 u

形象地说，就是"本来我以为到 v 是这条老路，结果发现绕道 u 反而更近，那就改走 u 这条路"。这个"比较 + 更新"的过程就叫松弛。它贯穿 Dijkstra、Bellman-Ford、Floyd 三个算法，是整个"最短路径"主题的中心动作，请务必吃透。

Dijkstra 为什么要用贪心、贪心为什么只对非负权成立？ 这是最值得想明白、也是面试最爱深挖的点：

  • Dijkstra 每次从 Q 里选"当前代价最小"的 u 并定死它的最短路径。它敢这么做，依赖一个关键前提：如果所有边权非负，那么已经确定的、代价最小的 u，不可能再被某个还没确定的路径"抄近道"变短了——因为任何能走向 u 的"更近"绕路，都必须经过某个 Q 中的点，而那个点现在离 s 的距离不可能比 u 更近（因为 u 已经是 Q 中最小的了），再加上边权非负（绕路只会加代价不会减），所以绕路永远是"折腾"，不能把 u 变短。
  • 一旦出现负权边，这个保证立刻崩塌：一个暂时"离 s 还远"的顶点 w，可能通过一条负权边被"负运输"，让"绕到 u"变比想象的短，于是你之前"定死 u 是最短"就错了。这就是"Dijkstra 不能处理负权"的根本原因，下面会用负权例子专门演示它怎么"翻车"。

Dijkstra 的复杂度：朴素实现（每次都扫一遍找最小的 u）是 O(n²)；用优先队列（最小堆）优化后是 O((n+e)·logn)。课件给的是邻接矩阵版 O(n²)。这里我给一个基于前面邻接矩阵 Graph 类的、朴素 O(n²) 的实现，逻辑最清晰，方便对照课件：

// ---- 加到 Graph 类里的 Dijkstra ----
// src: 源点；dist: 出参，dist[i]=s 到 i 的最短权值和；parentPath: 出参，记录每个顶点的"上一个顶点"用于还原路径
void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
{
    size_t N = _vertexs.size();
    size_t srci = GetVertexIndex(src);
 
    // dist：记录 srci 到其他顶点的最短路径权值数组，先全部设为"不可达"
    dist.resize(N, MAX_W);
    // parentPath：记录 srci 到其他顶点最短路径上每个顶点的"父顶点"（前驱下标），-1 表示还没有前驱
    parentPath.resize(N, -1);
    // 标记集合 S：visited[i]==true 表示顶点 i 已确定最短路径
    vector<bool> S(N, false);
 
    // 源点到自己的距离设为一个"最小合法值"（0 或默认），让贪心第一轮能选中源点
    dist[srci] = W();
 
    // 每个顶点都要确定一次最短路径，共循环 N 次
    for (size_t i = 0; i < N; ++i)
    {
        // 贪心：在"未确定"的顶点里挑 dist 最小的那个 u
        W min = MAX_W;
        size_t u = srci;
        for (size_t j = 0; j < N; ++j)
        {
            if (S[j] == false && dist[j] < min)
            {
                min = dist[j];
                u = j;                 // u 是当前"最有把握最短"的顶点
            }
        }
        S[u] = true;                   // 把 u 移入集合 S（确定其最短路径）
 
        // 松弛：对 u 的所有能到达且尚未确定的邻居 k，尝试更新更短路径
        for (size_t k = 0; k < N; ++k)
        {
            if (S[k] == false
                && _matrix[u][k] != MAX_W          // u 能直接到 k
                && dist[u] + _matrix[u][k] < dist[k])  // 经 u 更短
            {
                dist[k] = dist[u] + _matrix[u][k]; // 更新最短权值和
                parentPath[k] = u;                 // 记录前驱 u，用于还原路径
            }
        }
    }
}
 
// 打印从 src 出发、到每个顶点的最短路径和权值（基于 dist 和 parentPath 反推整条路径）
void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& parentPath)
{
    size_t N = _vertexs.size();
    size_t srci = GetVertexIndex(src);
    for (size_t i = 0; i < N; ++i)
    {
        if (i == srci) continue;              // 跳过源点自己到自己的路径
        cout << _vertexs[src] << " -> " << _vertexs[i] << " 最短距离: ";
        if (dist[i] == MAX_W)                 // 不可达
        {
            cout << "不可达" << endl;
            continue;
        }
        // 从终点 i 沿 parentPath 一路回溯到源点，收集路径
        vector<int> path;
        int p = (int)i;
        while (p != (int)srci && p != -1)
        {
            path.push_back(p);
            p = parentPath[p];
        }
        path.push_back((int)srci);
        reverse(path.begin(), path.end());    // 反转成从源点到终点的顺序
        cout << "路径: ";
        for (size_t pos = 0; pos < path.size(); ++pos)
        {
            cout << _vertexs[path[pos]];
            if (pos + 1 < path.size()) cout << "->";
        }
        cout << "  总权值: " << dist[i] << endl;
    }
}

配合一个可编译的测试（接在 Graph 类后面，使用课件那组 "syztx" 的图）演示 Dijskstra 的正常工作：

void TestDijkstra()
{
    // 顶点集合 syztx，有向图
    const char* str = "syztx";
    Graph<char, int, INT_MAX, true> g(str, strlen(str));
    g.AddEdge('s', 't', 10);
    g.AddEdge('s', 'y', 5);
    g.AddEdge('y', 't', 3);
    g.AddEdge('y', 'x', 9);
    g.AddEdge('y', 'z', 2);
    g.AddEdge('z', 's', 7);
    g.AddEdge('z', 'x', 6);
    g.AddEdge('t', 'y', 2);
    g.AddEdge('t', 'x', 1);
    g.AddEdge('x', 'z', 4);
 
    vector<int> dist;
    vector<int> parentPath;
    g.Dijkstra('s', dist, parentPath);
    g.PrintShortPath('s', dist, parentPath);
}

（TestDijkstra 需要 #include <cstring> 以使用 strlen。）

Dijkstra 为什么不能处理负权：一个"翻车"演示

我明说结论并用例子证明它：Dijkstra 一旦遇到负权边，贪心策略就失效，某些顶点的最短路径会算错。 这是面试的死知识点，务必理解到"换条路就翻车"的程度。

负权翻车的类型有两种，我分开讲，因为它们的严重程度不同：

类型一（轻微）：存在负权边但没有负环，且负权边出现在"已确定"顶点之后才被"激活"时，可能导致个别路径漏更新为正确最短值。 课件里的注释正好演示了这个经典例子，顶点 {s,y,t,x}：

s --10--> t
s --5----> y
t ---(-7)--> y      <-- 负权边
y --3----> x
从 s 出发：
Dijkstra 会先确定 s（0），再挑最小：s 到 y=5，到 t=10，挑 y(5) 定为最短。
此时给 y 的所有邻居松弛：y->x=3，则 x=5+3=8。
接着 S={s,y}，Q={t,x}；t 现在是 10，x 现在是 8，挑 x(8) 定为最短（其实 s->?->x 最优是 …… 我们先看 t）
S={s,y,x}；只剩 t：t 当前是 10。
Q 空吗？还没有。回到一开始——细细一看，本条链路：s->t(10) 再 t->y(-7) 得 y=3，比 5 更短！但 y 早就被定死了(5)，没机会更新了。

这就是问题所在：因为存在负权边 t->y=(-7)，从 s 经 t 再到 y 只有 10-7=3，比"直连的 5"更短，但 Dijkstra 很早就把 y 定为 5 并钉死了，根本没机会发现绕道 t 反而便宜。所以课件注释说"可以看到 s->t->y 之间的最短路径没更新出来"——这就是负权让贪心失效的铁证。它不是因为"有负环而无解"，而是因为贪心提前定死了一个本来还能被绕路优化掉的顶点。

类型二（致命）：存在负权回路。 如果图中存在一个环，环上权值之和为负（比如 s->a(1), a->b(-2), b->s(1)，环和 = 0 不是负；要环和 < 0 才算负环），那么从某点出发绕这个负环一圈，总权值还能继续减少，可以无限绕、越绕越便宜，最短路径不存在（权值和可以趋近负无穷）。对负环，任何"找最短路径"的算法（Dijkstra 自然也不适用于这种图）都必须能检测出来并报告"无界/无最短路径"，而 Dijkstra 做不到这一点（它甚至会陷入混乱或给出错误结果）。

给你的工程准则：Dijkstra 只能用于权值全非负的图。若题目保证非负权，优先用 Dijkstra（最快）；若含负权但无负环，换 Bellman-Ford（下文）；若疑似负权回路，用 Bellman-Ford 检测负环。

单源最短路径：Bellman-Ford 算法（可解负权）

Bellman-Ford 算法解决的是 Dijkstra 解不了的场景：带负权边（只要没有负权回路）的单源最短路径问题，并且它还能判断图中是否存在负权回路。

Bellman-Ford 的核心思想：对所有边进行"松弛"，而且要整体做 n-1 轮（n 是顶点数），每一轮把所有边都尝试松弛一遍。为什么是 n-1 轮？

这个可以这样理解：从源点 s 出发，不经过重复顶点的最短路径（简单路径）最坏要经过 n-1 条边（路径最多包含 n 个顶点，顶点数量 n 意味着最多 n-1 条边）。而每一轮松弛，都能保证"以『恰好经过一条新边』为代价的最短距离"被更新到位；也就是说：

第 1 轮后：s 到所有"走 ≤1 条边可达"顶点，距离最优。
第 2 轮后：s 到所有"走 ≤2 条边可达"顶点，距离最优。
……
第 k 轮后：s 到所有"走 ≤k 条边可达"顶点，距离最优。

因为一条最短路最多用 n-1 条边，所以只要连续松弛 n-1 轮，保证所有顶点的最短路径都算到位了。这就是"n-1 轮"的来历。

为什么 Bellman-Ford 不怕负权（但怕负环）：因为它不靠贪心一次定死，而是让每个顶点在 n-1 轮里始终保留"被更短路径覆盖"的机会——只要某条更短绕路依赖的边在更早某轮出现过，后续轮次就总能被松弛到。但如果有负权回路，那么路径所经边数可以无限扩充，超过 n-1 轮仍能继续变短（因为绕负环一圈权值和还减小），此时 n-1 轮结束后的"答案"就不是最小值——所以算法做法是 n-1 轮跑完后，再对所有边做一次"校验松弛"，若还能再变短，说明存在负权回路，返回失败。

复杂度：O(n·e)（n 轮 × 每轮 e 条边）。若用邻接矩阵实现遍历所有边是 O(n²)，则整体 O(n³)。这明显比 Dijkstra 的 O(n²) 高，所以只有出现负权才用它。

邻接矩阵版本的核心代码（逻辑和 Dijkstra 共有"松弛"，但多了一层"对每条边都松弛、并做 n-1 轮 + 负环校验"）：

// ---- 加到 Graph 类里的 Bellman-Ford ----
// 返回 true 表示没有负权回路、dist/parentPath 可用；返回 false 表示检测到负权回路
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
{
    size_t N = _vertexs.size();
    size_t srci = GetVertexIndex(src);
 
    dist.resize(N, MAX_W);        // 最短路径权值数组，全置"不可达"
    parentPath.resize(N, -1);     // 前驱数组
    dist[srci] = W();             // 源点到自己是 0，作为松弛起点
 
    // 做 n-1 轮松弛
    for (size_t k = 0; k < N - 1; ++k)
    {
        bool exchange = false;    // 记录这一轮是否有过更新，若没有说明已收敛，可提前终止
        for (size_t i = 0; i < N; ++i)          // 起点 i
        {
            for (size_t j = 0; j < N; ++j)      // 终点 j
            {
                // 松弛：srci->i + i->j 若比 srci->j 更短，则更新
                if (_matrix[i][j] != MAX_W
                    && dist[i] != MAX_W          // 注意：防止把不可达的 i 参与进来（溢出生效）
                    && dist[i] + _matrix[i][j] < dist[j])
                {
                    dist[j] = dist[i] + _matrix[i][j];
                    parentPath[j] = i;
                    exchange = true;             // 标记本轮有更新
                }
            }
        }
        if (exchange == false)   // 这一轮所有边都没能再优化，提前结束
            break;
    }
 
    // 负环检测：n-1 轮之后，若还能再松弛成功，说明存在负权回路
    for (size_t i = 0; i < N; ++i)
    {
        for (size_t j = 0; j < N; ++j)
        {
            if (_matrix[i][j] != MAX_W
                && dist[i] != MAX_W
                && dist[i] + _matrix[i][j] < dist[j])
            {
                return false;    // 还有边能继续变短 -> 有负环
            }
        }
    }
    return true;                 // 无负环，dist 即最终答案
}

这个实现里藏着一个容易踩的坑，我特意加了一行 dist[i] != MAX_W 的判断：用邻接矩阵做 Bellman-Ford 时，很多初学版本漏掉"源点根本到达不了 i"的情况，导致 dist[i] 还是 MAX_W（如 INT_MAX），再与负权边相加可能溢出或误以为更短，从而把"不可达"的顶点算成了"可达"。加了判空，才严谨。

多源最短路径：Floyd-Warshall 算法

Floyd-Warshall（弗洛伊德，也常简称 Floyd）算法解决的是多源最短路径问题：一次性求出图中任意两点之间的最短路径。它是个"以空间换时间"的动态规划，本质是三维 DP，但可以空间优化成二维。

它的核心思想（动态规划）：设 dist[i][j] 表示从 i 到 j 的最短距离。Floyd 的巧妙之处在于，它枚举"中间结点 k"，不断尝试用 i -> k -> j 来更新 i -> j：

依次把 k = 0,1,2,...,n-1 作为"允许中转点"：
若 dist[i][k] + dist[k][j] < dist[i][j]
则 dist[i][j] = dist[i][k] + dist[k][j]

课件帮你理清的本质：Floyd 算法原本是三维动态规划 D[i][j][k]，表示"从 i 到 j、中途顶点只属于 {0..k} 集合"的最短路径。递推转移是经典的"要么不走 k 号中转点，要么走 k 号中转点"：

D[i][j][k] = min( D[i][j][k-1],              // 不用 k 当中转
                  D[i][k][k-1] + D[k][j][k-1] )  // 用 k 当中转

因为这个 DP 的最外层只依赖 k-1 的结果，可以把第三维压缩掉，得到直接在二维 dist 上不断迭代的版本（这就是课件说的"空间优化掉最后一维"）。为什么二维直接覆盖是安全的？因为第 k 轮更新 dist[i][k] 或 dist[k][j] 时，k 中转点对于这两个位置不会产生更优的"绕 k"效果（以 k 为中转不会自环变短，除非有负环，而多源一般假定无负环），所以原地更新是安全的。

Floyd 的优点：支持负权边（只要无负环），一遍跑完得到所有点对距离。复杂度 O(n³)，空间 O(n²)。因为三个循环嵌套，n 不能太大（几百以内合适），这是它的主要限制。

核心实现（vvDist 是 n×n 的距离矩阵，vvParentPath 存前驱便于还原路径）：

// ---- 加到 Graph 类里的 Floyd-Warshall ----
// vvDist[i][j]: i 到 j 的最短距离； vvParentPath[i][j]: 从 i 到 j 的最短路径上，j 的前一个顶点
void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath)
{
    size_t N = _vertexs.size();
 
    // 初始化距离矩阵和前驱矩阵
    vvDist.resize(N);
    vvParentPath.resize(N);
    for (size_t i = 0; i < N; ++i)
    {
        vvDist[i].resize(N, MAX_W);
        vvParentPath[i].resize(N, -1);
    }
 
    // 用图的边直接初始化
    for (size_t i = 0; i < N; ++i)
    {
        for (size_t j = 0; j < N; ++j)
        {
            if (_matrix[i][j] != MAX_W)       // i 能直达 j
            {
                vvDist[i][j] = _matrix[i][j];
                vvParentPath[i][j] = static_cast<int>(i); // i->j 的直接前驱是 i
            }
            if (i == j)                        // i 到自身距离为 0，无前驱
            {
                vvDist[i][j] = W();
                vvParentPath[i][j] = -1;
            }
        }
    }
 
    // 依次用每个顶点 k 作为中转点，尝试松弛所有 i->j
    for (size_t k = 0; k < N; ++k)
    {
        for (size_t i = 0; i < N; ++i)
        {
            for (size_t j = 0; j < N; ++j)
            {
                // i->k 与 k->j 都可达，且经 k 更短，则更新
                if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
                    && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
                {
                    vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                    // 关键：i 到 j 经由 k 后，j 的前驱应更新为"k 到 j 那一段的前驱"
                    vvParentPath[i][j] = vvParentPath[k][j];
                }
            }
        }
    }
}

有一点要特别讲清楚：Floyd 能处理负权边，但不能处理负权回路。原因很直白——如果有负环，vvDist[i][i]（i 到自己的最短距离）会随着绕负环变成负数且在迭中不断被压缩，最终难以收敛出正确答案。做题时如果题目保证无负环，Floyd 就是求"任意两点最短路"的首选；若可能负环，校验一下 vvDist[i][i] 是否为负即可初步怀疑有负环。

三个最短路算法的小结对比（划重点）：

算法解决问题能否含负权是否能检测负环复杂度（邻接矩阵）
Dijkstra单源不能不能O(n²)
Bellman-Ford单源能（无负环）能O(n³)（邻接矩阵）/ O(n·e)（邻接表）
Floyd-Warshall多源（任意两点）能（无负环）能（看 dist[i][i] 是否变负）O(n³)

一句话：非负权用 Dijkstra；有负权无负环能用 Bellman-Ford 或 Floyd；怀疑负环用 Bellman-Ford 检测。 选错算法，是这块最常见的灾难性错误。

最小生成树

长时间铺垫后，终于到课件最后一个大块：最小生成树（Minimum Spanning Tree, MST）。先回到概念。

最小生成树的来历：对于一个连通图（无向带权），它的生成树是我们上面定义的"有 n 个顶点、n-1 条边、连通且无环"的最小子图。当图的边带权值时，生成树有很多棵，我们要找边权总和最小的那一棵，这就是最小生成树。

课件里给了化成生成树的"极大无环子图"的说法，并与几条构造准则对应。先把三个准则背牢（它们是 MST 的"宪法"）：

  1. 只能使用图中的边来构造最小生成树。
  2. 只能使用恰好 n-1 条边来连接图中的 n 个顶点。
  3. 选用的 n-1 条边不能构成回路。

MST 为什么不是"贪心全局最优矛盾"：最小生成树是少数几个"贪心算法能得到全局最优解"的问题之一（因为 MST 满足"拟阵"的数学结构），所以课件里那句"贪心算法做的不一定是整体最优解"要这样理解——贪心算法在大多数问题上得不到全局最优（比如后面会看到最短路径里 Dijkstra 就因负权翻车），但在 MST 问题上恰好成立。所以 Kruskal、Prim 这两个贪心算法能正确地解出 MST。

Kruskal 算法（加边法 / 选边法）

Kruskal（克鲁斯卡尔）算法的思路是"不断从剩余的边中选权值最小的边，只要不形成环就加入"，其英文思想也被叫"加边法"：

任给一个有 n 个顶点的连通网络 N={V,E}：

  1. 首先构造一个由这 n 个顶点组成、不含任何边的图 G={V, ∅}，此时每个顶点自成一个连通分量；
  2. 不断从 E 中取出权值最小的一条边（若有多条，任取其一），若该边的两个顶点来自不同的连通分量（即这条边不会让G内成环），则将此边加入 G；
  3. 如此重复，直到 G 中所有顶点都在同一个连通分量上（即选够了 n-1 条边）为止。

核心：每次迭代时，选出一条权值最小且两端点不在同一连通分量上的边，加入生成树。

实现它的关键支撑有三个：

  • 优先队列（最小堆）：把所有边按权值塞进一个最小堆，每次 pop 出权值最小的边。放课件里就是 priority_queue<Edge, vector<Edge>, greater<Edge>> pq。
  • 并查集（Union-Find）：判断一条边的两个顶点"是否已在同一连通分量（会不会成环）"。若它们的根不一样，安全，加进来并把它们所属的两个分量"合并"；若根相同，说明它们已经被前面的边连成一条了，这条边会构成环，跳过。并查集是 Kruskal 的灵魂，没有它无法高效判环。
  • 边数控制：加到 n-1 条边时结束；若最后边数不够 n-1，说明原图本就不连通，无生成树。

课件里给的 Kruskal(Self& minTree) 正确体现了这个流程，我把逻辑用完整可编译的版本梳理出来，并用一个手写的极简并查集（路径压缩 + 按秩）支撑它，凑成一个能跑的完整程序：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>     // strlen
using namespace std;
 
// 极简并查集：用于维护"顶点是否已连通"（给 Kruskal 判环用）
class UnionFind
{
public:
    UnionFind(int n) : _parent(n), _rank(n, 0)
    {
        for (int i = 0; i < n; ++i) _parent[i] = i;  // 初始每个人自己是一组
    }
    int find(int x)   // 路径压缩查找根
    {
        if (_parent[x] != x) _parent[x] = find(_parent[x]);
        return _parent[x];
    }
    bool unite(int a, int b)   // 合并两个集合，若本就在一组返回 false
    {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;        // 已在同一分量，会成环
        if (_rank[ra] < _rank[rb]) swap(ra, rb);
        _parent[rb] = ra;
        if (_rank[ra] == _rank[rb]) ++_rank[ra];  // 按秩合并
        return true;
    }
private:
    vector<int> _parent, _rank;
};
 
// 边（用于存进最小堆）
struct Edge
{
    int _srci, _dsti, _w;      // 起点下标、终点下标、权值
    Edge(int s = 0, int d = 0, int w = 0) : _srci(s), _dsti(d), _w(w) {}
};
bool operator>(const Edge& a, const Edge& b) { return a._w > b._w; } // 小根堆用 greater
 
// 带权无向图（邻接矩阵版，足够演示 MST）
class MGraph
{
public:
    MGraph(const char* ver, int n) : _n(n)
    {
        _vertexs.assign(ver, ver + n);
        _matrix.assign(n, vector<int>(n, INT_MAX));
    }
    int idx(char v) { for (int i = 0; i < _n; ++i) if (_vertexs[i] == v) return i; return -1; }
    void add(char a, char b, int w)
    {
        int i = idx(a), j = idx(b);
        _matrix[i][j] = _matrix[j][i] = w;   // 无向图，对称填
    }
 
    // Kruskal 求最小生成树，返回权值和；若不连通返回 -1
    int Kruskal(vector<Edge>& mst)
    {
        // 1. 把所有边按权值放进最小堆（i<j 避免无向图重复入堆）
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        for (int i = 0; i < _n; ++i)
            for (int j = i + 1; j < _n; ++j)
                if (_matrix[i][j] != INT_MAX)
                    pq.push(Edge(i, j, _matrix[i][j]));
 
        UnionFind uf(_n);        // 维护顶点的连通分量
        int total = 0, cnt = 0;  // cnt 是已选边数
        while (!pq.empty() && cnt < _n - 1)   // 最多选 n-1 条
        {
            Edge e = pq.top(); pq.pop();
            if (uf.unite(e._srci, e._dsti))    // 两端不在同一分量 -> 不构成环
            {
                mst.push_back(e);
                total += e._w;
                ++cnt;
            }
        }
        return cnt == _n - 1 ? total : -1;     // 若没选满 n-1 条，说明图不连通，无 MST
    }
 
private:
    vector<char> _vertexs;      // 顶点
    vector<vector<int>> _matrix; // 邻接矩阵
};
 
int main()
{
    // 课件那组经典最小生成树测试数据（9 个顶点 a~i）
    MGraph g("abcdefghi", 9);
    g.add('a','b',4);  g.add('a','h',8);
    g.add('b','c',8);  g.add('b','h',11);
    g.add('c','i',2);  g.add('c','f',4);  g.add('c','d',7);
    g.add('d','f',14); g.add('d','e',9);
    g.add('e','f',10);
    g.add('f','g',2);
    g.add('g','h',1);  g.add('g','i',6);
    g.add('h','i',7);
 
    vector<Edge> mst;
    int total = g.Kruskal(mst);
    if (total == -1)
        cout << "图不连通，无最小生成树" << endl;
    else
    {
        cout << "Kruskal 最小生成树权值和: " << total << endl;
        cout << "边: ";
        for (auto& e : mst) cout << "(" << e._srci << "-" << e._dsti << ":"
                                 << e._w << ") ";
        cout << endl;
    }
    return 0;
}

Kruskal 复杂度：把所有边排序 O(e·loge)（或用堆构建 O(e log e)），加上每次并查集 find/unite 近似 O(1)（路径压缩），整体 O(e·loge)。显然，边数越少越划算，所以 Kruskal 适合稀疏图。

Kruskal 的一个隐蔽坑：加边时"两端点根相同"= 会成环，必须跳过。这个判断完全靠并查集正确维护，一旦并查集写错（比如没路径压缩导致 find 慢、或 unite 逻辑弄反），MST 就会加进成环的边而出错。我在上面用 unite 返回 false 表示"已在一组"，直接映射这个判环逻辑，很清晰。

Prim 算法（加点法 / 选点法）

Prim（普里姆）算法与 Kruskal 相反：它不是选边，而是从一个起点出发，不断把"离当前已选顶点集合最近的新顶点"拉进来，其英文思想叫"加点法"：

  1. 任选一个顶点 src 作为起点，把它放入"已在生成树中的顶点集合"（记为 inSet）；
  2. 反复找到一条一头连接 inSet 内顶点、另一头连接 inSet 外顶点的权值最小的边，把这条边和它带进来的新顶点一并加入生成树；
  3. 当所有 n 个顶点都进入 inSet 时，选满 n-1 条边，得到最小生成树；若最终没选满，说明图不连通。

实现思路：用优先队列存"从 inSet 顶点出发的候选边"，每次取权值最小的边，若边的另一头（新顶点）不在 inSet 内就加入并把它引出的新边再放进队列。典型实现用 priority_queue + 一个 set（或 bool 数组）表示 inSet。

这里我想特别点一个很多人写的 Prim 版会踩的 bug：单纯在弹边的时候判断"两个端点是否都在 inSet 内"不够严谨，会导致某些情况漏加或错加。更稳妥的写法是每次只认"把新顶点带进来"的边（即被弹出来的边中，有一个端点不在 inSet 内），并把新顶点引出的边再推入堆。写成课件那样的判定条件是合理的：

if (inSet 里没有 min._srci 或 inSet 里没有 min._dsti)
    -> 说明这条边能带来新顶点，加入生成树，并把新顶点引出的未入 sets 的边推入堆

下面给一个可编译的 Prim（邻接矩阵版），用 bool 数组 代替 set 更方便：

// ---- 加到上面 MGraph 类里：Prim 最小生成树（从顶点 s 下标在本图方法内传字符） ----
// 用最小生成树角度，s 作为起始顶点，返回权值和；不连通返回 -1
int Prim(const char& src, vector<Edge>& mst)
{
    int srci = idx(src);
    vector<bool> inSet(_n, false);   // inSet[i]==true 表示顶点 i 已在生成树集合内
    inSet[srci] = true;              // 起点先放进去
 
    // 最小堆，存候选边
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    // 把从 src 出发的所有边放进候选堆
    for (int i = 0; i < _n; ++i)
        if (_matrix[srci][i] != INT_MAX)
            pq.push(Edge(srci, i, _matrix[srci][i]));
 
    int total = 0, cnt = 0;          // cnt 是已选边数
    while (cnt < _n - 1 && !pq.empty())
    {
        Edge min = pq.top(); pq.pop();
        // 这条边必须能带来一个"不在集合里"的新顶点，才有效
        if (!inSet[min._srci] || !inSet[min._dsti])
        {
            mst.push_back(min);
            total += min._w;
            ++cnt;
            // 新进来的顶点记为 newv（那条边的另一端不在 inSet 里的那个）
            int newv = inSet[min._srci] ? min._dsti : min._srci;
            inSet[newv] = true;      // 把新顶点放入集合
            // 把新顶点引出的、指向未被选顶点集合的边都放进候选堆
            for (int i = 0; i < _n; ++i)
                if (_matrix[newv][i] != INT_MAX && !inSet[i])
                    pq.push(Edge(newv, i, _matrix[newv][i]));
        }
    }
    return cnt == _n - 1 ? total : -1;   // 选满 n-1 条才成功
}

Prim 复杂度：邻接矩阵版 O(n²)，邻接表+堆版 O((n+e)·logn)。因为复杂度与边数关系不如 Kruskal 的 O(e·loge) 直接，一般说 Prim 更适合稠密图、Kruskal 更适合稀疏图。

Kruskal 与 Prim 的选择：两道"最小生成树选择题"的标准答案，建议记下来——

  • Kruskal：不断选最小边、配合并查集判环；稀疏图（边少）更优。
  • Prim：从点出发、不断拉最近的未连通点；稠密图（边多）更优。

两者算法基石不同（Kruskal 靠并查集，Prim 靠优先队列 + 集合），但都正确求出 MST，因为 MST 满足贪心选择的数学前提（拟阵性质）。

最小生成树 vs 最短路径的"概念陷阱"

很多初学者会把"最小生成树"和"最短路径"搞混，这里我一定帮你划清界限，因为这是概念理解的关键分水岭：

对比项最小生成树（MST）最短路径（Dijkstra 等）
求解目标连接所有顶点的边权总和最小的连通子图（n-1 条边、无环）两个指定顶点之间一条路经的权值和最小
结果形态一棵树（连所有点）通常是点到点的一条路径
关注"边总数"固定 n-1 条边路径可长可短（简单路径内）
例子建空前最小成本的通信骨干网北京到上海最短的驾车路线

一句话记忆：MST 是"把所有点连通的最小成本"，最短路是"两个点之间最小的行进成本"。前者看整幅图、连一网；后者看具体两点、走一条路。二者不可混用——比如"求北京到上海最短路"用 Dijkstra 而非 Kruskal，因为 Kruskal 连的"全图网络"跟"单点对距离"完全是两码事。

总结与心智模型

图这一章，我们用一条主线贯通：先定义图（顶点+边、有向/无向、度、连通性）、再想办法存（邻接矩阵 OR 邻接表，按稠密/稀疏选）、然后用 BFS/DFS 遍历（记得 visited 和连通分量兜底）、接着在 DAG 上做拓扑排序（Kahn 算法）、最后钻研两个优化大问题（最短路径的 Dijkstra/Bellman-Ford/Floyd，最小生成树的 Kruskal/Prim）。

把所有算法的"选型指南"浓缩成一张决策表，这是你复习时的"复习地图"：

我要解决什么问题用哪个算法关键坑
遍历图（层序感知）BFS（队列）入队即标 visited；非连通要兜底
遍历图（深挖/判连通）DFS（递归/栈）递归栈深；非连通要兜底
DAG 排先后顺序拓扑排序（Kahn）必须无环；入度算准
单源最短路（权非负）Dijkstra不能有负权
单源最短路（可能有负权、无负环）Bellman-Ford循环 n-1 轮 + 负环检测
任意两点最短路（无负环）Floyd-WarshallO(n³)，n 不能太大
最小生成树（稀疏图）Kruskal并查集判环
最小生成树（稠密图）Prim只认"能带新顶点进集合"的边

图这个主题信息密度很高，但框架非常清晰。下面给一组带详解答案的思考题，不是为了考倒你，而是让你用手脑再走一遍"知识点 → 实际计算"的链路，很多看似抽象的定义，一旦落到具体的数上立刻就会宽松。

思考题（含详解答案）

下面 6 道题覆盖本节核心，每道都给了完整推导，请先自己作答，再对答案。

题 1：一个有 8 个顶点的无向完全图有几条边？一个有 8 个顶点的有向完全图有几条边？

答案：无向完全图 n*(n-1)/2 = 8*7/2 = 28 条；有向完全图 n*(n-1) = 8*7 = 56 条。有向完全图每条"点对"有两个方向相反的有向边，所以数量正好是无向的两倍。

题 2：在某有向图中，已知顶点 A 的入度为 3、出度为 2，那么 A 的度是多少？该图所有顶点入度之和与出度之和之间有什么关系？

答案：A 的度 = 入度 + 出度 = 3 + 2 = 5。对所有顶点，入度之和恒等于出度之和（也等于有向边总数），因为每条有向边给一个起点贡献 1 出度、给一个终点贡献 1 入度，两侧各自被数了一次，所以总和必然相等。

题 3：如果一个无向图有 4 个顶点和 3 条边（边分别是 (v0,v1)、(v1,v2)、(v2,v3)），它有几个连通分量？从 v0 出发做 BFS，能否访问到全部顶点？

答案：4 个顶点连成一条链，所有顶点彼此连通，所以只有 1 个连通分量（它是连通图）。从 v0 出发，BFS 沿链一层层走：v0 → v1 → v2 → v3，可以访问到全部顶点。因为这里图是连通的，BFS 只需一次启动（配合 visited）即可遍历完。若此图增加一个孤立的第 5 个顶点（没有任何边），连通分量就会变成 2 个，此时从 v0 出发的 BFS 无法到达孤立顶点，必须靠"兜底循环"再启动一次。

题 4：为什么 Dijkstra 算法要求边的权值必须非负？举一个会因为负权而出错的简单例子。

答案：Dijkstra 是贪心算法，它每次挑"当前 dist 最小"的顶点 u 后，就永久确定 u 的最短路径。这个"确定"成立的前提是：任何能走向 u 的更短绕路，都必须经过一个"还没确定"的顶点，而这个顶点的 dist 不可能小于 u 的 dist（因为 u 已是未确定中最小），再加上非负权不会让绕路减少总代价，所以绕路不可能把 u 压得更小。一旦有负权边，这个前提就碎了：一个"当前 dist 较大"的顶点 w，可以通过一条负权边把"绕向 u"的代价拉低，导致之前被定死的 u 实际上有更短路径。

例子：顶点 s、t、y，有向边 s->t=10、s->y=5、t->y=-7（负权）。从 s 出发，Dijkstra：

  • 第一轮，未确定顶点里 s 到 y=5 最小，把 y 定为 5；
  • 此时给 t 松弛，s 到 t 是 10；
  • 下一轮把 t(10) 定为最短。 结果 Dijkstra 输出 y=5、t=10。但真实最短：s->t(10) + t->y(-7) = 3，即 s 到 y 实际最短是 3，比 5 还小！就因为 y 过早被"钉死"在 5，错过了经 t 的负权捷径——贪心在负权面前失效了。这也验证了"路径权值为负时，贪心定死顶点会算错"。

题 5：拓扑排序对一个有向图来说，什么情况下 "排不满" ?这能判断什么 ?

答案：当有向图存在**回路（环）**时，会产生互相矛盾的依赖（A 须在 B 前，B 须在 A 前），导致某些顶点永远不可能被排进去，最终排出的顶点数少于顶点总数。Kahn 算法正是利用"排满与否"来检测图中是否有环：若最终排出的顶点数 == n，说明无环（DAG），拓扑排序成功；若 < n，说明有环。这个"用拓扑排序判环"的能力，常被用来检验工程任务编排里是否存在死锁/循环依赖。

题 6（综合）：一个 6 顶点的连通带权无向图（顶点 A..F），给出如下边：A-B=1、B-C=3、A-C=4、A-D=6、B-D=7、C-E=8、D-E=9、E-F=2。用 Kruskal 求最小生成树的边和总权值。若改成求 A 到 F 的最短路径，和最小生成树一样吗？

答案：用 Kruskal 全程（把边按权值升序，依次判断两端点是否同分量，若不同则选、否则跳过）：

  • 收集所有边升序：AB=1, EF=2, BC=3, AC=4, AD=6, BD=7, CE=8, DE=9。
  • 选 AB=1（分量 {A},{B} → 合并 {A,B}）。
  • 选 EF=2（{E},{F} → {E,F}）。
  • 选 BC=3（{A,B} 与 {C} → {A,B,C}）。
  • 选 AC=4：A、C 已在 {A,B,C}，同分量，成环 → 跳过。
  • 选 AD=6（{A,B,C} 与 {D} → {A,B,C,D}）。
  • 选 BD=7：B、D 已在 {A,B,C,D}，跳过。
  • 选 CE=8（{A,B,C,D} 与 {E,F} → {A,B,C,D,E,F}），此时 6 个顶点全部连通，已选 n-1=5 条：AB、EF、BC、AD、CE。
  • 总权值 = 1+2+3+6+8 = 20。

所以 MST 是 {A-B, B-C, A-D, C-E, E-F}（5 条），总权值 20。（可以验证去掉成环边后权值和最小。）

再看 A→F 最短路径：沿权值找 A 到 F 最省的走法。图上可选路径有 A-F 没有直接边；候选好路线：A-B-C-E-F = 1+3+8+2=14；A-D-E-F=6+9+2=17；A-C-E-F=4+8+2=14；A-B-D-E-F=1+7+9+2=19。最短是 14（不止一条，比如 A-B-C-E-F 或 A-C-E-F 都=14）。结论：MST（连通全图，权值和 20）与"两点 A→F 的最短路径（一条路，权值 14）"是两个不同的东西，权值、边集都不同。这正是前面"概念陷阱"一节的绝佳数据印证：MST 连所有点、看整体；最短路连两点、看局部。

好，图这一章完整走完了。从"长什么样的数据结构"到"怎么存、怎么走、怎么排先后、怎么求最短和最小连通"，咱们顺着这一条线把图的骨架全部打进了你的脑子里。下次不管是在笔试题里遇到"判断是否强连通""给依赖图排执行顺序""求地图两点最短路"，还是工程里分析网络拓扑、任务调度，这套知识和决策表都能直接派上用场。图的难点从来不是代码本身，而是面对问题先想清楚"用哪个存储、哪个算法、有没有边界陷阱"——只要方向选对，剩下的就是你已经练熟的模板。多写几遍、多跑几组数据，图会成为你最趁手的数据结构之一。

（本讲基本概念与代码思想参考了《算法导论》与《殷人昆 · 数据结构：用面向对象方法与 C++ 语言描述（第二版）》的表述与框架。）