本文介绍图论相关内容。

1 图的基本概念

图（Graph）由顶点集和边集组成，记为G=\{V,E\}。边集E可以为空，但顶点集V一定非空，即图至少要有一个顶点（因此无“空图”这种说法）。图中的一部分顶点与边构成的图称为子图（Subgraph，又称生成图）。边上赋予的数值称为边的权值，带权的图称为⽹（Network）。

根据边有无方向划分：

• 有向图（Directed Graph）：边为有向边（弧）的图，从顶点u至v的弧记为\left \langle u,v \right \rangle，两端分别称为弧头和弧尾
• 无向图（Undirected Graph）：边为⽆向边的图，顶点u与v的边是顶点的无序对，记为(u,v)

简单图与多重图：⽆重边、⽆⾃环的图称为简单图，否则称为多重图【数据结构通常只研究简单图】

稀疏图与稠密图：边数⼩于n\log n的图称为稀疏图，否则称为稠密图

更多定义详见下文。

---

2 图的重要理论性质

顶点的度：

• ⽆向图中，顶点的度\text{TD}(v)为邻接于顶点v的边的条数，全部顶点的度数之和等于边数的2倍，即\sum\limits_i \text{TD}(v_i)=2|E|
• 有向图中，顶点的⼊度\text{ID}(v)为指入顶点v的边（入边）的条数，顶点的出度\text{OD}(v)为从顶点v指出的边（出边）的条数，顶点的度\text{TD}(v)=\text{ID}(v)+\text{OD}(v)，全部顶点的入度之和等于出度之和，且都等于边数，即\sum\limits_i \text{ID}(v_i)=\sum\limits_i \text{OD}(v_i)=|E|

【总结与归纳】图的度相关计算

1. 由度与边数的关系可知：⽆向图中，所有顶点度的和必为偶数
2. 任何图中度为奇数的顶点个数为偶数个

路径、环、路径⻓度：

• 路径：由⼀些顶点及对应的边组成的顶点序列。若第⼀个顶点与最后⼀个顶点相同则称为回路（环）
  • 判断环的方法：DFS、拓扑排序、求关键路径…
• 简单路径、简单回路：顶点不重复出现的路径、回路。当|E|>|V|-1时，必定有回路
• 路径长度：路径中的边数或边权之和
• 距离：两个顶点的最短路径⻓度称为两点间的距离，若不存在路径，则记距离为⽆穷（\infty）或其他特殊记号

完全图：

• 无向完全图：任意两个顶点之间都存在边的⽆向图，有\dfrac{n(n-1)}{2}条边
• 有向完全图：任意两个顶点之间都存在⽅向相反的两条弧的有向图，有n(n-1)条弧

连通、连通图、连通分量：

• 连通：⼀对顶点u与v之间，从顶点u到v有路径存在
• 连通图：任意两个顶点都是连通的⽆向图。n个顶点的连通图至少有n-1条边，至多有\dfrac{n(n-1)}{2}条边
• 连通分量：⾮连通图中的极⼤连通⼦图（包含边数最多）

强连通、强连通图、强连通分量：

• 强连通：⼀对顶点u与v之间，从u到v和从v到u都有路径存在
• 强连通图：任意两个顶点都是强连通的有向图。n个顶点的强连通图至少有n条边，至多有n(n-1)条边
• 强连通分量：⾮强连通图中的极⼤强连通⼦图

⽣成树（⽆向树）：连通图/连通分量中包含图中全部顶点的⼀个极⼩连通⼦图（边数最少）。生成树的性质如下

1. 对于n个顶点的图，生成树有且仅有n-1条边；故对⽣成树⽽⾔，砍去⼀条边则变为⾮联通图，加上⼀条边则构成环
2. 只要⽆向连通图中没有权值相同的边，则其最⼩⽣成树必唯⼀；但当存在权值相同的边时，其最⼩⽣成树可能唯⼀也可能不唯⼀（因为可能该图本身就是树）

有向树：⼀个顶点的⼊度为0、其余顶点的⼊度均为1的有向图，若⼲棵不相交的有向树组成⽣成森林

【总结与归纳】图的综合计算题

1. 有28条边的⾮连通⽆向图⾄少有多少个顶点？
   • 【分析】先套完全图边数公式算出顶点数n，再加1即可
   • 【解】当图为完全图时，解\dfrac{n(n-1)}{2}=28得n=8，则⾮连通图的最少顶点数为8+1=9
2. 要保证含有n个顶点的无向图G在任何情况下（即任意变动图中的边）都是连通的，则需要的边数最少是？
   • 【解】先取其中任意n-1个顶点构成完全连通子图，即产生\dfrac{n(n-1)}{2}条边，再将该子图与剩下的顶点添1条边即可，故总计至少需要\dfrac{n(n-1)}{2}+1条边

---

3 图的存储结构

预定义两种类型：

• VexType：顶点信息的类型，可为int（序号）、double（操作数）、char（运算符、字母）等
• EdgeType：边信息的类型，无权图中可用bool或int指示边是否存在，带权图中可用int或double存储权值（无边则为\infty）

⽆向图可以⽤存两条有向边的⽅式存储，故在存储结构中不作区分

【拓展】实际应用中常使用如2.B中所介绍的链式前向星存储树与图：

1. 邻接矩阵：注意无法存储重边，因此通常选择存储所有重边权中的最值。适合存稠密图，可随机存取任意边

int g[N][N];    // g[a][b]存储有向边<a, b>

/* 初始化 */
void init() {
    memset(g, 0x3f, sizeof g);
}

/* 获取边<a, b> */
int get(int a, int b) {
    return g[a][b];
}

2. 邻接表：相当于同时开n条无头单链表，表h[k]存储点k的所有出边。适合存稀疏图，可快速遍历某点的所有出边。可直接使用二维std::vector实现，或手动用数组实现n叉静态链表：

const int N = 1e5, M = 2 * N;

int n, m;   // 点数、边数
int h[N], e[M], ne[M], idx;     // h[k]为点k的边表的头指针

/* 初始化 */
void init() {
    memset(h, -1, sizeof h);
    idx = 0;
}

/* 添加一条边<a, b> */
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

vector<vector<int> > g; // 使用vector容器
vector<int> g[N];   // 另一种写法

typedef pair<int, int> PII; // <vertex, weight>

vector<vector<PII> > g; // 同时存储出边的边权

3.1 邻接矩阵

邻接矩阵（Adjacent Matrix）：⽤⼆维数组（邻接矩阵）存储图中的边的信息。

• 无权图：\text{1}表示存在边，\text{0}表示不存在边
• 带权图：存在边则存储边的权值（⾃身到⾃身可记为\text{0}），不存在边则记\infty或其他特殊记号

#define MAXSIZE 55

typedef struct MGraph {
    VexType vex[MAXSIZE];   // 顶点信息数组
    EdgeType edge[MAXSIZE][MAXSIZE];    // 邻接矩阵，存储边的信息
    int v, e;   // 图的基本信息：顶点数、边数
} MGraph;   // 邻接矩阵图

特点：

1. 空间复杂度：O(|V|^2)
2. 稠密图适合⽤邻接矩阵存储
3. 寻找给定点的邻边需遍历⼀整⾏/列；但可随机存取，能⽴刻判断边的存在性
4. ⽆向图的邻接矩阵是对称矩阵且唯⼀，故实际只需存储上/下三⻆部分的元素（详见“特殊矩阵的压缩存储”）
5. 度的计算
   • ⽆向图中：第i行/列非零非\infty元素的个数为顶点v_i的度\text{TD}(v_i)
   • 有向图中：G->edge[i][j]表示弧\left \langle v_i,v_j \right \rangle，第1维射出，第2维射⼊
     • 第i行非零非\infty元素的个数为顶点i的出度\text{OD}(v_i)
     • 第j列非零非\infty元素的个数为顶点v_j的入度\text{ID}(v_j)

3.2 邻接表

邻接表（Adjacent List）：对每个顶点建⽴⼀条单链表存储该顶点出边的信息，头指针采⽤顺序存储（一维数组），整个结构即为邻接表

1. 边表：结点结构与单链表完全相同，记录了出边的弧尾结点以及边的权值
2. 顶点表：将各链表的头指针与对应的顶点信息存于⼀维数组中

#define MAXSIZE 55

typedef struct ArcNode {
    EdgeType data;  // 边的信息
    int adjvex; // 邻接顶点的序号
    struct ArcNode *nextarc;    // 后继指针
} ArcNode;  // 边表结点

typedef struct VNode {
    VexType data;   // 顶点信息
    ArcNode *firstarc;  // 指向边表的第⼀条边（相当于头指针）
} VNode;    // 顶点结点

typedef struct AGraph {
    VNode adjlist[MAXSIZE]; // 顶点表，存放各边表的头指针
    int v, e;   // 图的基本信息：顶点数、边数
} AGraph;   // 邻接表图

特点：

1. 空间复杂度：无向图为O(|V|+2|E|)，有向图为O(|V|+|E|)
   • 对于⽆向图，相当于每条“有向边”出现了两次，故为如此
2. 稀疏图适合⽤邻接表存储，时空效率上远优于邻接矩阵
3. 寻找给定点的邻边只需遍历边表即可；但⽆法随机存取，判断边的存在性亦需进⾏遍历
4. 度的计算：出度直接等于顶点边表的⻓度，⼊度则需遍历全表统计
   • 改进⼊度的计算：再建⽴⼀个逆邻接表
5. 根据存图时的遍历顺序，邻接表的表示⽅式不唯⼀

3.3 其他存储结构

⼗字链表：存储有向图。与5.2.2中稀疏矩阵的存储⽅法略有不同，存图时的结构体特点如下：

• 弧结点：tailvex、headvex分别存储弧尾、弧头顶点编号，hlink、tlink分别指向弧头、弧尾相同的下一个弧，info存储弧的相关信息（如权值）
• 顶点结点：data存储顶点数据，firstin、firstout分别指向以该顶点为弧头、弧尾的第一个弧结点

邻接多重表：存储⽆向图，每条边只需⼀个结点存储（了解即可）

• 表结点：mark、ivex、ilink、jvex、jlink、info
• 顶点结点：data、firstedge

边的结构体：很多情景（如顶点覆盖问题）着重考察边（及其两个端点）的性质（如连通性），这些性质通常与多点宏观关系（如路径）无关，并且该情况下常采用顶点对的形式读入数据，因此适合使用简单结构体数组存储。这种数据结构的空间利用率高于邻接矩阵，相对于邻接表更方便直接遍历所有边。需要操作大量集合时也常与并查集结合使用（如Kruskal算法）

typedef struct Edge {
    int a, b;   // 边的起点与终点（默认为有向边<a, b>）
    EdgeType w; // 边的权值（Weight）
} Edge;

可当场定义结构体数组，示例如下：

struct edge {
    int a, b;
    int w;
} e[N];

---

4 图的遍历

图的遍历⽅式同样适⽤于树，但遍历图需使⽤访问标记数组visited[]标记已被遍历过的顶点。

DFS与BFS的应用极为广泛，并不局限于图。限于篇幅，本文暂仅给出图的遍历代码示例。

4.1 深度优先遍历

深度优先遍历（Depth-First-Search，DFS）：类似于树与二叉树的先序遍历，常⽤递归

• 效率：
  • 时间复杂度：邻接矩阵图为O(|V|^2)，邻接表图为O(|V|+|E|)
  • 空间复杂度：O(|V|)（使用了递归工作栈）
• 图的DFS代码示例：

/* 邻接矩阵图的DFS算法 */
void dfs(MGraph *G, int v, bool visited[]) {
    visit(v);   // 访问顶点
    visited[v] = true;  // 置访问标记为true
    for (int i = 0; i < G->v; i++)  // 遍历邻接矩阵的第v⾏
        if (G->edge[v][i] && !visited[i])
            dfs(G, i, visited);
}

/* 邻接表图的DFS算法 */
void dfs(AGraph *G, int v, bool visited[]) {
    visit(v);   // 访问顶点
    visited[v] = true;  // 置访问标记为true
    ArcNode *p = G->adjlist[v].firstarc;
    while (p) { // 沿着链表访问未访问过的顶点
        if (!visited[p->adjvex]) dfs(G, p->adjvex, visited);
        p = p->nextarc;
    }
}

/* 封装DFS函数（两种图皆适⽤） */
void dfsTraverse(Graph *G, int v) {
    bool visited[MAXSIZE] = {0};    // 访问标记数组，初始化全为false，被访问则置true
    dfs(G, v, visited); // 从起点v开始遍历
    for (int i = 0; i < G.v; i++)   // 检查是否有未被遍历到的顶点
        if (!visited[i])
            dfs(G, i, visited);
}

DFS技巧：

• 分析问题：画图、归纳
• 保存现场
• 剪枝
• 偏移量：适用于各种DFS、BFS等矩阵遍历情形。控制点在二维平面上移动的方向（搜索方向），可设定方向下标按顺时针（上、右、下、左）递增。此时对于方向下标i，其反方向下标为i ^ 2（对2做按位异或运算），亦可手动if设置求得。

  // 上(-1, 0)，右(0, 1)，下(1, 0)，左(0, -1)
  int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

4.2 广度优先遍历

⼴度优先遍历（Breadth-First-Search，BFS）：类似于树与二叉树的层序遍历，使⽤了辅助队列

• 性能：
  • 时间复杂度：邻接矩阵图为O(|V|^2)，邻接表图为O(|V|+|E|)
  • 空间复杂度：O(|E|)（使用了队列）
• 图的BFS代码示例：

/* 邻接矩阵图的BFS算法 */
void bfs(MGraph *G, int v, bool visited[]) {
    Queue Q;
    initQueue(Q);
    visit(v);   // 访问起点
    visited[v] = true;  // 置访问标记为true
    push(Q, v); // 将起点⼊队
    while (!isEmpty(Q)) {
        pop(Q, v);
        for (int i = 0; i < G.v; i++) { // 遍历邻接矩阵的第v⾏
            if (G->edge[v][i] && !visited[i]) {
                visit(i);   // 访问邻接顶点
                visited[i] = true;  // 置访问标记为true
                push(Q, i); // 将邻接顶点⼊队
            }
        }
    }
}

/* 邻接表图的BFS算法 */
void bfs(AGraph *G, int v, bool visited[]) {
    Queue Q;
    initQueue(Q);
    visit(v);   // 访问起点
    visited[v] = true;  // 置访问标记为true
    push(Q, v); // 将起点v⼊队
    while (!isEmpty(Q)) {
        pop(Q, v);
        ArcNode *p = G->adjlist[v].firstarc;
        while (p) { // 沿着链表访问未访问过的顶点
            int k = p->adjvex;
            if (!visited[k]) {
                visit(k);   // 访问邻接顶点
                visited[k] = true;  // 置访问标记为true
                push(Q, k); // 将邻接顶点⼊队
            }
            p = p->nextarc;
        }
    }
}

/* 封装BFS函数（两种图皆适⽤） */
void bfsTraverse(Graph *G, int v) {
    bool visited[MAXSIZE] = {0};    // 访问标记数组，初始化全为false，被访问则置true
    bfs(G, v, visited); // 从起点v开始遍历
    for (int i = 0; i < G.v; i++)   // 检查是否有未被遍历到的顶点
        if (!visited[i])
            bfs(G, i, visited)
}

BFS技巧：

• 必要时开距离数组记录第一次到达每个点时的距离（即为到达每个点的最短路距离）
• 求多源最短路时，可以设立一个超级源点（指向各源点的出边权值为0），则将问题转化为从超级源点到终点的单源最短路径。实际用BFS求时只需在初始化时将所有源点一次性入队即可。

4.3 图DFS与BFS的应用

判断图的连通性：连通图条件为生成树的边数为顶点数（dfs(1) == n）。从任意顶点出发遍历⼀次，检查标记数组是否全标记即可

• 【拓展】使用DFS与BFS均可实现连通性判断，以下给出DFS示例：

int n;
bool g[N][N], st[N];

/* DFS检测连通性。连通图条件：生成树的边数为顶点数 dfs(1) == n */
int dfs(int u) {
    st[u] = true;
    /* 可额外添加“输出”、“入vector”、“计入权值”等操作，以下递归入口前后同理 */

    int res = 1;    // 可走到的顶点数
    for (int i = 1; i <= n; ++i)
        if (!st[i] && g[u][i])
            res += dfs(i);

    return res;
}

• 【拓展】使用并查集计算图中的连通块（连通分量）数量（建议使用边的结构体存储各边）：
  • 法一：用变量cnt记录当前连通块的数量（初始化为顶点数，有时根据题意会事先剔除k个顶点则再减k），遍历边数组，使用并查集合并每条边的两个端点（若符合题意），每合并一条就将cnt自减1。最后cnt即为所求结果，cnt - 1即为恢复成连通图需要添加的最少边数。
  • 法二：合并顶点操作同法一，但不实时记录连通块数量，合并结束后从头遍历并查集，其中的祖宗结点个数即为结果（与上同理，如有特殊要求则需减去剔除的顶点数）。

DFS⽣成树、BFS⽣成树：根据DFS、BFS的轨迹所得的⽣成树，⾮连通图的⽣成树组成⽣成森林

• ⽣成树的⾼度⽐较：
  • 对于⼀些特殊的图（例如只有⼀个顶点的图），其BFS⽣成树的树⾼和DFS⽣成树的树⾼相等。
  • 对于⼀般的图，根据图的BFS⽣成树和DFS树的算法思想， BFS⽣成树⽐DFS⽣成树矮。综上，h_{\text{BFS树}}≤h_{\text{DFS树}}
• 邻接矩阵图的⽣成树是唯⼀的，邻接表图的⽣成树根据链表初始化⽅式⽽变

计算单源最短路径：当图中各边权值相等时（例如迷宫），可⽤BFS计算单源最短路径

---

5 图的应用

最小生成树、最短路径、DAG存储表达式、拓扑排序、关键路径…

5.1 最小生成树

最⼩⽣成树（Minimum Spanning Tree，MST）：带权⽆向连通图中权和（代价）最⼩的⽣成树

5.1.1 Prim算法

Prim算法：“加点法”，每次迭代选择代价最⼩的边对应的点。常使用邻接矩阵图进行计算。与Dijstral算法极为相似。

辅助变量：

• lowcost[]：最小代价数组，存储其他点到当前⽣成树的最短距离（邻接则为出边权，不邻接则为\infty）
  • 注：与Dijstra算法的距离数组不同，Prim算法的最⼩代价数组记录的是到整棵树的距离
• visited[]：标记数组，标记点是否已经在⽣成树中

算法过程：

1. 第⼀次代谢：任取⼀顶点（常为序号1）作为⽣成树T
2. 选择剩余顶点中与当前⽣成树距离最近（lowcost值最小）的顶点，将该顶点与对应的边（权值）并⼊T（权和）
3. 从新并⼊顶点出发，更新lowcost[]（注：为到整棵树的距离，故无需累加至历史值）；反复执⾏2、3两步， 共|V|-1次

算法性能分析：时间复杂度为O(|V|^2)，只跟顶点数有关，因此适⽤于稠密图，即边稠密⽽顶点较少

/* 计算从顶点v出发构建的最⼩⽣成树的最⼩代价，⽤sum返回结果 */
void prim(MGraph *G, int v, EdgeType *sum) {
    EdgeType lowcost[MAXSIZE];  // 最⼩代价数组，记录当前⽣成树到其他各顶点的最短距离
    bool visited[MAXSIZE] = {0};    // 标记数组，记录顶点是否并⼊⽣成树，初始均为未并⼊状态
    for (int i = 0; i < G->v; i++) {
        lowcost[i] = G->edge[v][i]; // 初始化最⼩代价为源点v的出边权（或⽆穷）
    }
    *sum += G->vex[v];  // 并⼊源点
    visited[v] = true;
    for (int i = 0; i < G->v - 1; i++) {    // 进⾏(|V| - 1)次循环，每轮并⼊⼀个顶点⾄⽣成树
        EdgeType min = INF; // 记录当前⽣成树到其他顶点的最⼩距离
        for (int j = 0; j < G->v; j++) {    // 寻找剩余顶点中最⼩⽣成树最近的顶点
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                v = j;
            }
        }
        *sum += G->vex[v];  // 并⼊该顶点
        visited[v] = true;
        for (int j = 0; j < G->v; j++) {    // 更新当前最⼩⽣成树到剩余顶点的最⼩距离
            if (!visited[j] && lowcost[j] > G->edge[v][j]) {
                lowcost[j] = G->edge[v][j]; // 注：lowcost为到整棵树的距离
            }
        }
    }
}

5.1.2 Kruskal算法

Kruskal算法：“加边法”，按权值递增次序，每次迭代选择最⼩代价边。⾮常适合⼿⼯操作。

辅助变量：

• p[]：并查集数组（另见6.4.3），检查顶点是否属于不同集合（树）时使⽤
• edges[]：Kruskal算法的存图⽅式为边的结构体（如7.2.3中所述），存储所有边的信息

算法过程：

1. 将图中的所有边按代价从⼩到⼤排序（详见“排序”，任选一种排序算法即可）；将图中的n个顶点看成独⽴的n棵树组成的森林
2. 从⼩到⼤选择边，所选的边的两个端点应属于两棵不同的树，则成为⽣成树的⼀条边，并将这两颗树合并作为⼀颗树
3. 重复第2步，直至所有顶点都在⼀棵树内，或有n-1条边为⽌

算法性能分析：时间复杂度为O(|E|\log_2 |E|)，只跟边数有关，因此适⽤于稀疏图，即边稀疏⽽顶点较多

typedef struct {
    int a, b;
    int w;
} Edge;

int p[MAXSIZE]; // 并查集数组，注意此处存储范围为[0, |V| - 1]

/* 并查集核心操作——查找（同6.4.3） */
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

/* Kruskal算法 */
void kruskal(MGraph *G, Edge edges[], int *sum) {
    for (int i = 0; i < G->v; i++) {    // 初始化并查集数组
        p[i] = i;
    }
    sort(edges, G->e)   // 将边的结构体数组中的|E|条边按权值升序排序
    for (int i = 0; i < G->e; i++) {
        int a = find(edges[i].a), b = find(edges[i].b);
        if (a != b) {   // 非同一子树则并入
            p[a] = b;
            *sum += edges[i].w;
        }
    }
}

注：使⽤Prim算法和Dijstral算法⽣成的MST是相同的

5.2 最短路径

最短路径的性质：最短路径⼀定是简单路径，不存在环

5.2.1 Dijkstra算法

Dijkstra算法：求单源最短路径，⽆法处理含负权边的图。常使用邻接矩阵图进行计算。通常仅要求掌握朴素Dijkstra算法。

辅助变量：

• dist[]：距离数组，存储其他点到源点S的最短距离(邻接则为边权，不邻接则为\infty)
• path[]：路径数组，记录前驱结点，算法结束时可根据\text{path}[i]追溯得源点S到任意连通顶点v_i的最短路径
• visited[]：标记数组，标记点的最短路是否已经确定

算法过程：

1. 将源点到源点的距离\text{dist}[S]设定为\text{0}
2. 选择剩余顶点中到源点S的路径最短（dist值最小）的顶点v_t
3. 根据新选择的顶点v_t，更新dist[]与path[]（注：为到源点S的最短距离，故与整条路径作比较，需累加历史值）；反复执⾏2、3两步， 总共|V|-1次

算法性能分析：时间复杂度为O(|V|)，适用于稠密图

/* 求以v为源点的单源最短路径，存储于dist[]、path[] */
void dijkstra(MGraph *G, int v, EdgeType dist[], int path[]) {
    bool visited[MAXSIZE] = {0};    // 标记数组，记录点的最短路是否已经确定，初始均为未加⼊路径状态
    for (int i = 0; i < G->v; i++) {
        dist[i] = G->edge[v][i];    // 初始化距离为源点的出边权或⽆穷
        if (G->edge[v][i] < INF) {  // 源点与该点邻接，则该点的前驱为源点
            path[i] = v;
        } else {        // 否则置为-1
            path[i] = -1;
        }
    }
    path[v] = -1;   // 规定源点的前驱为-1，让其加⼊路径
    visited[v] = true;
    for (int i = 0; i < G->v - 1; i++) {    // 进⾏(|V| - 1)次循环，每轮确定⼀个顶点的最短路径
        EdgeType min = INF; // 记录当前未确认顶点中的最⼩距离
        for (int j = 0; j < G->v; j++) {    // 寻找剩余顶点中距离源点最近的顶点
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                v = j;
            }
            visited[v] = true;  // 标记该点已加⼊最短路径
            for (int j = 0; j < G->v; j++) {    // 更新剩余未确认顶点到源点的距离，同时更新路径
                if (!visited[j] && dist[j] > dist[v] + G->edge[v][j]) {
                    dist[j] = dist[v] + G->edge[v][j];
                    path[j] = v;
                }
            }
        }
    }
}

/* 打印从源点v到⽬标顶点a的最短路径，其中path[]已⽤dijkstra()求得 */
void printPath(int path[], int a) {
    int stack[MAXSIZE], top = -1;   // 初始化顺序栈
    while (path[a] != -1) { // 从a⼀路往上⾄源点依次⼊栈
        stack[++top] = a;
        a = path[a];
    }
    stack[++top] = a;   // 最后让a也⼊栈
    while (top != -1) { // 将栈内顶点倒出访问
        visit(stack[top--]);
    }
}

【拓展】堆优化Dijkstra算法：使用堆（优先队列）加快最近顶点的选取

• 时间复杂度：O(|E|\log |V|)
• 适用情形：稀疏图

typedef pair<int, int> PII;

int n;  // V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx;   // 邻接表图，w[i]存边i的权值
int dist[N];    // dist[]存储起点到每个点的最短路径
bool st[N];     // st[]标记每个点的最短路是否已被确定

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int dijkstra(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;    // 这里也只先设起点的dist

    priority_queue<PII, vector<PII>, greater<PII> > heap;   // 小根堆
    heap.push({0, S});      // (distance, vertex)

    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int u = t.second, distance = t.first;   // 用堆得到最近的点及与其距离

        if (st[u]) continue;    // 若已确定则跳过
        st[u] = true;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] > distance + w[i]) {
                dist[v] = distance + w[i];
                heap.push({dist[v], v});
            }
        }
    }

    if (dist[T] == 0x3f3f3f3f) return -1;
    return dist[T];
}

5.2.2 Floyd算法

Floyd算法：基于动态规划，求多源最短路径，可以含负权边，但不允许包含带负权边的回路。常使用邻接矩阵图进行计算。

相关参数：

• A_k：n\times n距离矩阵序列，规定初始状态A_{-1}为邻接矩阵，A_k[i][j]表示以顶点v_k作为中间点时顶点v_i到v_j的最短距离
• \text{Path}_k：n\times n路径矩阵序列，用来记录当前两顶点最短路径上要经过的中间点，规定初始状态\text{Path}_{-1}的全部元素为-1

算法过程：

1. 初始化距离矩阵A_{-1}为邻接矩阵，路径矩阵\text{Path}_{-1}的全部元素为-1
2. 顺次枚举中间点v_k，更新A_k=\min(A_{k-1}[i][j],A_{k-1}[i][k]+A_{k-1}[k][j])，同时更新\text{Path}_{k}将其逐渐加⼊路径
3. 循环第2步n次即得最终的距离矩阵A_{n-1}和路径矩阵\text{Path}_{n-1}

【总结与归纳】路径矩阵序列\text{Path}的特点：

• 当最短路径发⽣更改时，\text{Path}_{k-1}就不再是\text{Path}_k的子集

算法性能分析：时间复杂度为O(|V|^3)

/* 求图G各顶点的最短路径，存储于矩阵A[][]、path[][] */
void floyd(MGraph *G, int A[][MAXSIZE], int path[][MAXSIZE]) {
    for (int i = 0; i < G->v; i++) {    // 初始化矩阵
        for (int j = 0; j < G->v; j++) {
            A[i][j] = G->edge[i][j];
            path[i][j] = -1;
        }
    }
    for (int k = 0; k < G->v; k++) {    // 枚举中间点，将中间点逐步加⼊路径，并修改矩阵
        for (int i = 0; i < G->v; i++) {
            for (int j = 0; j < G->v; j++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

/* 打印任意两点之间的最短路径，其中矩阵A[][]、path[][]已⽤floyd()求得 */
void printPath(int i, int j, int A[][MAXSIZE], int path[][MAXSIZE]) {
    if (A[i][j] < INF) {
        if (path[i][j] != -1) {
            visit(i, j);    // 打印这条边
        } else {
            int mid = path[i][j];   // 中间点
            printPath(i, mid, A, path); // 递归打印前半段路径
            printPath(mid, j, A, path); // 递归打印后半段路径
        }
    }
}

5.2.A Bellman-Ford算法*

时间复杂度：O(|V| \cdot |E|)

适用情形：存在负权边的图

int n, m;       // V: [1 ... n]
struct Edge {
    int a, b, w;
} edges[M];     // 边集，存储权值为w的有向边<a, b>
int dist[N];    // dist[]存储起点到每个点的最短路径

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellmanFord(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for (int i = 0; i < n; i++) {   // 要求最大长度为n的最短路径，故迭代n次
        for (int j = 0; j < m; j++) {   // 每次遍历全部m条边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w) {    // 松弛操作：更新当前dist
                dist[b] = dist[a] + w;
            }
        }
    }

    if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;    // 因为负权边的存在，可能略低于INF
    return dist[T];
}

应用：求有边数限制的最短路

• 时间复杂度：O(|V| \cdot |E|)
• 思路：限制k条边就进行k轮迭代遍历，遍历开始前需先备份 dist[]于 backup[]，用其将 dist[]更新

int n, m, k;    // 限制最短路最多经过k条边
struct Edge {
    int a, b, w;
} edges[M];
int dist[N], backup[N]; // backup[]备份dist[]数组，防止发生串联（用改后数据去改别人）

/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellmanFord(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for (int i = 0; i < k; i++) {   // 限制k条边，则迭代k次
        memcpy(backup, dist, sizeof dist);  // 遍历边前先将dist拷贝至备份数组
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > backup[a] + w) {  // 使用备份数组做松弛操作
                dist[b] = backup[a] + w;
            }
        }
    }

    if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
    return dist[T];
}

5.2.B SPFA算法*

时间复杂度：平均O(|E|)，最坏O(|V|\cdot |E|)

队列优化的Bellman-Ford算法，后继变小了当前dist才变小

int n;          // V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx;   // 邻接表图，w[i]存边i的权值
int dist[N];    // dist[]存储起点到每个点的最短路径
bool st[N];     // st[]标记每个点的最短路是否已被确定

int spfa(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    queue<int> q;   // 队中存放待更新的点（用堆也行）
    q.push(S);
    st[S] = true;   // 结点入队时做标记

    while (!q.empty()) {    // 使用BFS的思想
        auto t = q.front();
        q.pop();

        st[t] = false;  // 结点出队时撤销标记（之后可能需再次入队被更新）

        for (int i = h[t]; ~i; i = ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) {
                dist[u] = dist[t] + w[i];
                if (!st[u]) {   // 若更新了u的距离，则其出边所指也可能待更新，判断将其入队
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }

    if (dist[T] == 0x3f3f3f3f) return 0x3f3f3f3f;
    return dist[T];
}

应用：判断图中是否存在负环

• 时间复杂度：O(|V|\cdot |E|)
• 特点：不需要初始化dist[]，因此之后正权入边顶点永不会被更新。并且为了消除某点可能无法到达负环的影响，将所有点全入队并标记！
• 原理：若某条最短路径上有n个点（除了自己），则加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，故存在负环。

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];    // cnt[x]存储起点（任意）到x的最短路中经过的点数
bool st[N];

/* 如果存在负环，则返回true，否则返回false */
bool spfa() {
    queue<int> q;   // 不需要初始化dist数组，直接将所有点全入队并标记！
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) {
                dist[u] = dist[t] + w[i];
                cnt[u] = cnt[t] + 1;    // 若更新了u的距离，则立即更新其cnt（前驱加1）
                if (cnt[u] >= n) return true;   // 若最短路已包含至少n个点（不含自身），则有负环
                if (!st[u]) {
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }

    return false;   // 跳出循环则说明无负环
}

5.3 有向无环图存储表达式

有向⽆环图（Directed Acyclic Graph，DAG）：不存在环的有向图，任意结点都⽆法通过⼀些有向边回到⾃身

存储表达式的建图⽅法：

1. 将表达式中出现的所有不同的操作数排成⼀排，作为最底层（出度为0）结点
2. 让运算符结点按照运算优先级（先算 → 后算）指向对应其左右操作元素的结点（可能是操作数或前⼀级运算符），尽可能利用已结合操作数的前⼀级运算符
3. 递归进⾏第2步操作

相较于表达式二叉树，表达式DAG的结点数更少，计算效率更高。

【例】表达式((a + b) * (b * (c + d)) + (c + d) * e) * ((c + d) * e)分别在⼆叉树和DAG中的存储：

5.4 拓扑排序

基本概念：

• AOV网（Activity-On-Vertex Network，活动在顶点上的⽹）：顶点表示活动、边表示活动的先后次序的有向无环图。
• 拓扑排序（Topological Sort）：对DAG的顶点进⾏排序，使得对存在的每⼀条有向边\left \langle v_a,v_b \right \rangle，顶点v_a排在v_b之前。常使用邻接表图进行操作。手工求解非常轻松。

对AOV⽹进⾏拓扑排序的⽅法：

1. 事先准备入度数组indegree[]记录图中所有顶点的⼊度
2. 从AOV⽹中将⼊度为0的结点输出并删除，然后将所有从其指出的顶点的⼊度减1
3. 反复指向第2步，最终若所有顶点都被访问则排序成功；否则说明该⽹不是AOV⽹，排序失败

算法性能分析：时间复杂度为O(|V|+|E|)

/* 对邻接表图进行拓扑排序，其中indegree[]事前记录了所有顶点的⼊度 */
bool topoSort(AGraph *G, int indegree[]) {
    int cnt = 0;    // 统计已被访问的顶点数量
    int stack[MAXSIZE], top = -1;   // 存放入度为0的顶点的容器（此处为栈，亦可选用队列）
    for (int i = 0; i < G->v; i++) {    // 获取所有入度为0的顶点
        if (indegree[i] == 0) {
            stack[++top] = i;
        }
    }
    while (top != -1) {
        int v = stack[top--];   // 弹出一个入度为0的顶点并访问
        visit(v);
        cnt++;
        ArcNode *p = G->adjlist[v].firstarc;
        while (p) { // 修改所有出边对应的邻接顶点的⼊度，同时获取所有⼊度为0的顶点
            int k = p->adjvex;
            indegree[k]--;
            if (indegree[k] == 0) {
                stack[++top] = k;
            }
            p = p->nextarc;
        }
    }
    if (cnt == G->v) return true;   // 访问了全部顶点，排序成功
    return false;   // 否则排序失败
}

【总结与归纳】拓扑序列的性质

1. 因为⼀个顶点可能存在多条出边指向不同顶点，故拓扑排序大部分情况下结果不唯⼀，除⾮顶点已经排在线性序列中
2. 若⼀个有向图有唯⼀拓扑序列，则其每个顶点的⼊度或出度也可能⼤于1，例如下图
   
3. 若⼀个有向图的顶点不能排成⼀个拓扑序列，则该有向图含有顶点数⼤于1的强连通分量

【例】如图所示的AOV⽹的全部拓扑序列为

1. v1, v6, v4, v3, v2, v5
2. v1, v3, v2, v6, v4, v5
3. v6, v1, v3, v2, v4, v5

逆拓扑排序：将拓扑排序中所有“⼊度”“⼊边”改为“出度”“出边”即可

• 实质：实际上与DFS序列中顶点的先后次序相同

5.5 关键路径

基本概念：

• AOE⽹（Activity-On-Edge Network，活动在边上的⽹）：边表示活动、顶点表示事件的有向无环图
  • 特点：边有权值，代表活动持续时间；顶点是新活动开始或旧活动结束的标志。只有某顶点代表的事件发⽣后，从顶点出发的各有向边代表的活动才能开始。只有某顶点所有⼊边代表的活动都结束时，顶点代表的事件才发⽣。
• 源点：⼯程⾥唯⼀⼀个⼊度为0的顶点；表示整个⼯程的开始
• 汇点：⼯程⾥唯⼀⼀个出度为0的顶点；表示整个⼯程的结束
• *关键路径（Critical Path）：具有最⼤路径⻓度的路径；是图中的最⻓路径，⼜是整个⼯期所完成的最短时间
• 关键活动：关键路径上的活动

重要参量及计算⽅法：

1. 事件v_k的最早发生时间ve(k)：该事件的最早发⽣时间，即途经源点到其的最⻓路径
   • 求法：令ve(源点)=0，按拓扑序列计算其他顶点从源点到自身的最⼤路径⻓度，直接作为结果，
2. 事件v_k的最迟发生时间vl(k)：不推迟整个⼯程完成的情况下，该事件最迟发⽣时间
   • 求法：令vl(汇点)=ve(汇点)，按逆拓扑序列计算其他顶点从自身到汇点的最⼤路径⻓度，再用vl(汇点)减去它。
3. 活动a_i的最早发⽣时间e(i)：该活动的起点所表示事件的最早发⽣时间（ve）
4. 活动a_i的最迟发⽣时间l(i)：该活动的终点所表示事件的最迟发⽣时间（vl），再减去该活动所需时间（权值w）
5. 活动a_i的剩余时间d(i)=l(i)-e(i)
   • 判定条件：若d(i)=0，则该活动a_i为关键活动

关键路径解题步骤：写出拓扑排序及逆拓扑排序，顺次计算所有参量，找出剩余时间为0的关键活动，拼成路径即可

【例】计算以下AOE⽹的关键路径：

【解】拓扑序列：v1, v2, v3, v4, v5, v6，逆拓扑序列：v6, v5, v4, v3, v2, v1

顶点	v1	v2	v3	v4	v5	v6
ve	0	3	2	6	6	8
vl	0	4	2	6	7	8

活动	a1	a2	a3	a4	a5	a6	a7	a8
e	0	0	3	3	2	2	6	6
l	1	0	4	4	2	5	6	7
d	1	0	1	1	0	3	0	1

\therefore关键路径上的边为a2, a5, a7

（本例的AOE网较为特殊，实际上求完ve、vl后即可直接作差得出最短路径为v1 → v3 → v4 → v6）

5.A 二分图*

定义：二分图可将图中顶点划分两个集合，使得集合内顶点互不邻接，不同集合顶点可邻接

定理：图为二分图\Leftrightarrow图中不含奇数环

5.A.1 染色法*

时间复杂度：O(|V|+|E|)

判断是否是二分图

思想：若为二分图，则与黑点相连的点均为白色，与白点相连的点均为黑色（邻接顶点不得同色）

int n;  // V: [1 ... n]
int h[N], e[M], ne[M], idx; // 邻接表图
int color[N];   // 每个点的颜色：-1未染色，0白色，1黑色

/* 用DFS给结点u染颜色c，一切顺利返回true，出现冲突则返回false */
bool dye(int u, int c) {
    color[u] = c;   // 给结点u染颜色c

    for (int i = h[u]; ~i; i = ne[i]) { // 遍历所有从结点u指出的点
        int v = e[i];
        if (color[v] == -1) {   // 若v未染色则将其染与u相反的色(!c)并判定是否冲突
            if (!dye(v, !c)) return false;
        } else if (color[v] == c) {
            return false;   // 若v与u同色则出现冲突
        }
    }
    return true;
}

/* 用染色法判断图是否是二分图 */
bool check() {
    memset(color, -1, sizeof color);
    for (int i = 1; i <= n; i++) {  // 遍历所有顶点，若未染色则染白色并判定是否冲突
        if (color[i] == -1) {
            if (!dye(i, 0)) {
                return false;
            }
        }
    }
    return true;
}

5.A.2 匈牙利算法*

时间复杂度：最差O(|V|\cdot |E|)（实际运行时间一般远小于O(|V|\cdot |E|)）

用于求二分图的最大匹配数（匹配：某两个点有且只有他们之间有边，与别人无边）

匈牙利算法中只会用到从第1个集合指向第2个集合的边，所以这里只用存一个方向的边。

int n1, n2;     // 二分图中两个集合的点数。集合1: [1 ... n1]、集合2: [1 ... n2]
int h[N], e[M], ne[M], idx; // 邻接表图，只存集合1到集合2的边
int match[N];   // match[i] = j表示集合2的点i当前匹配集合1的点j（j=0表示暂无匹配）
bool st[N];     // st[i]标记集合2的点i是否已经被遍历过

/* 寻找与集合1的点u匹配集合2的点，返回是否成功 */
bool find(int u) {
    for (int i = h[u]; ~i; i = ne[i]) { // "遍历所有可能"
        int v = e[i];
        if (!st[v]) {
            st[v] = true;
            if (match[v] == 0 || find(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

/* 求最大匹配数 */
int countMatches() {
    int res = 0;
    for (int i = 1; i <= n1; i++) { // 依次枚举集合1的每个点去匹配集合2的点
        memset(st, false, sizeof st);   // 每次重置遍历标记
        if (find(i)) {
            res++;
        }
    }
    return res;
}