算法题笔记

3.1 折半查找

核心要素：有序顺序表  |  时间 O(log n)  |  空间 O(1)

有两种模板。

int B_Search(int A[], int L, int R, int x){
    int mid;
    while(L <= R){                       // 只要区间不为空就继续
        mid = (L + R) / 2;
        if(A[mid] == x){
            return mid;                  // 查找成功
        }
        else if (A[mid] > x){
            R = mid - 1;
        }
        else    L = mid + 1;
    }
    return -1;                           // 查找失败
}

int B_Search(int A[], int L, int R, int x){
    int mid;
    while(L < R){                        // 缩小区间直到只有一个元素
        mid = (L + R) / 2;
        if (A[mid] >= x)	R = mid;     // 第一个符合条件的元素的下标在 L~mid
        else    L = mid + 1;             // 第一个符合条件的元素的下标在 mid+1~R
    }
    return L;                            // 可能成功也可能失败，需额外判断
}

3.2 散列表

使用条件：数据范围有限  |  时间 O(n)  |  空间 O(m)

核心思想

以空间换时间，创建辅助数组 count[]，count[i] 用于记录数值 i 出现的相关信息（如次数、是否出现等）。

🎯 什么时候用？

题目明示或通过分析确定元素值的范围时——例如元素值为 0 ~ n-1，或元素绝对值 < n ——马上考虑散列表。

⚠️ 注意：必须确保 A[i] 不超出 count 下标范围；新建辅助数组后一定初始化！

3.3 预处理 重难点

使用条件：频繁区间查询  |  预处理 O(n)  |  查询 O(1)

sum[0] = 0
sum[1] = A[0]
sum[2] = A[0] + A[1] = sum[1] + A[1]
sum[3] = A[0] + A[1] + A[2] = sum[2] + A[2]
...

void ans(int A[], int n) {
    // 定义结果数组并初始化
    int res[n];
    for (int i = 0; i < n; i++)
        res[i] = INT_MIN;
    // 定义前缀和数组
    int sum[n + 1] = {0};
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i-1] + A[i-1];
    // 枚举所有区间 [i, j] 并更新
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int temp = sum[j+1] - sum[i];
            if (temp > res[j-i])
                res[j-i] = temp;
        }
    // 输出 res 数组
}

void ans(int A[], int n) {
    int res[n], B[n];
    B[0] = INT_MIN;
    for (int i = 0; i < n; i++)
        B[i] = max(B[i-1], A[i]);
    for (int j = 0; j < n; j++)
        res[j] = B[j] * A[j];
    // 输出 res 数组
}

3.4 多指针法

使用条件：线性表（顺序表、链表），主要是有序线性表  |  时间视情况  |  空间 O(1)

适用情形：

• 多个线性表：每个线性表设置一个指针，如合并多个有序线性表
• 单个线性表：一个线性表中设置两个指针，如一前一后/一快一慢，用于查找或调整元素顺序

经典应用：合并多个有序线性表、寻找第 k 个元素、归并排序等。

void ans(int A[], int n) {
    int i = 0, j = n - 1;
    int pivot = A[0];                // 选第一个元素为基准
    while (i < j) {
        while (i < j && A[j] >= pivot)  j--;   // A[j] < pivot 时停
        while (i < j && A[i] <= pivot)  i++;   // A[i] > pivot 时停
        if (i < j)  swap(A[i], A[j]);          // 交换逆序对
    }
    swap(A[0], A[i]);                // 基准归位
}

1. 链表与顺序表的比较

2. 链表的定义

typedef struct LNode{
    ElemType data;                // 该结点的权值
    struct LNode *next;           // next 指向下一个结点
};

typedef struct LNode{
    ElemType data;                // 该结点的权值
    struct LNode *prior, *next;   // prior 指向上一个结点
};

3. 链表的基本操作

1. 删除结点 p

删除时注意两个问题：① 删除操作不要导致断链；② 要能找到下一次待处理的结点（p 要更新所指结点）。

pre->next = p->next;             // 将 pre 的 next 域指向 p 的下一个结点
p = p->next;                     // 将 p 指向 p 的下一个结点

删除时还需考虑释放结点所占内存（C 语言调用 free(p)），考试中为了方便不写也没关系。

加上 free 的写法：

pre->next = p->next;
LNode* temp = p;
p = p->next;
free(temp);

2. 将 p 插入 pre 后面

⚠️ 先后再前，这样一定不会断链！

p->next = pre->next;             // 先处理 p 的 next
pre->next = p;                   // 后处理 pre 的 next

先修改 pre 的 next 可能会找不到 pre 的下一个结点。

3. 尾插法和头插法

📥 尾插法

需要保证插入顺序与最终顺序一致时使用。设置 tail 指针始终指向链表末尾。核心三行：

p->next = NULL;                    // ① 将新结点的 next 置为 NULL
tail->next = p;                    // ② 将 tail 的 next 指向 p
tail = p;                          // ③ 更新 tail 为 p

📤 头插法

想让插入顺序与最终顺序相反时使用。将结点插入到头结点和第一个数据结点之间，常用于链表逆置。

void Head_Insert(Node* L, Node* p) {
    p->next = L->next;               // 先连后
    L->next = p;                     // 再连前
}

✅ 口诀：所有单链表插入都应该先连后，再连前。这样一定不会断链。

Node* p = L->next;
for (int i = 0; i < n; i++) {
    visit(p);                       // 访问 p 结点
    p = p->next;
}

Node* p = L->next;
while (p != NULL) {
    visit(p);                       // 访问 p 结点
    p = p->next;
}

Node* p = L->next;
int n = 0;
while (p != NULL) {
    n++;
    visit(p);                       // 访问 p 结点
    p = p->next;
}

4. 链表的两种暴力解

📌 例题：将链表 L 按照升序重新排序，结点结构为 data | next（带头结点单链表）

// 在有序链表中找到 p 的插入位置并插入
void Find_Insert(ListNode *pre, ListNode *p) {
    while (pre->next!=NULL && pre->next->data < p->data)
        pre = pre->next;
    p->next = pre->next;
    pre->next = p;
}
Node* ans(Node *L) {
    Node *p = L->next;
    L->next = NULL;
    while (p != NULL) {
        Node *temp = p->next;        // 暂存下一个
        Find_Insert(L, p);           // 将 p 插入到 L 中
        p = temp;                    // 处理下一个
    }
    return L;
}

void Qsort(int A[], int L, int R) {
    if (L >= R) return;
    int pivot, i = L, j = R;
    pivot = A[L];
    while (i < j) {
        while (i < j && A[j] >= pivot) j--;
        while (i < j && A[i] <= pivot) i++;
        if (i < j) swap(A[i], A[j]);
    }
    swap(A[L], A[i]);
    Qsort(A, L, i-1);
    Qsort(A, i+1, R);
}
Node* ans(Node *L) {
    int a[maxn], n = 0;
    Node *p = L->next;
    while (p != NULL) {              // 遍历保存到数组
        a[n] = p->data;  n++;
        p = p->next;
    }
    Qsort(a, 0, n-1);                // 数组排序
    p = L->next;
    for (int i = 0; i < n; i++) {    // 写回链表
        p->data = a[i];
        p = p->next;
    }
    return L;
}

5. 链表的优化解

// 归并两个升序链表
void Merge(LNode *L1, *L2) {
    // p 和 q 分别指向两个链表的第一个数据结点
    LNode *p = L1->next;
    LNode *q = L2->next;
    // 新建一个链表 L3，tail 指向其尾结点
    LNode *L3 = (LNode *)malloc(sizeof(LNode));
    LNode *tail = L3;
    // 合并过程，比较并链接
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;           // tail 始终指向尾结点
    }
    // 处理剩余结点，直接链接到 tail 后面
    if (p != NULL) tail->next = p;
    else tail->next = q;
    // 释放旧头结点，返回新链表
    free(L1);  free(L2);
    return L3;
}

Node *p, *q;
p = q = L->next;
while (p != NULL && q != NULL) {
    p = p->next;                     // p 走 1 步
    q = q->next;
    if (q == NULL) break;
    q = q->next;                     // q 走 2 步
    if (p == q) { /* 有环 */ }
}

Node *p, *q;
p = q = L->next;
while (p != NULL && q != NULL) {
    q = q->next;
    if (q == NULL || q->next == NULL) break;
    q = q->next;                     // q 走 2 步
    p = p->next;                     // p 走 1 步
    if (p == q) { /* 有环 */ }
}
// p 就是 q 的一半（即在中点）

Node *p, *q;
p = q = L;
for (int i = 0; i < k; i++)
    q = q->next;                     // q 先走 k 步
while (q != NULL) {
    p = p->next;                     // p、q 同步后移
    q = q->next;
}
// 此时 p 指向倒数第 k 个

// 链表版
void Hash_Linklist(Node* L) {
    int count[n] = {0};
    Node* p = L->next;
    while (p != NULL) {
        if (count[p->data] > 0)
            cout << p->data;         // 输出重复元素
        count[p->data]++;            // 记录 p->data 出现的次数
        p = p->next;
    }
}
// 顺序表版（对照）
void Hash_Sequence(int a[], int n) {
    int count[n] = {0};
    for (int i = 0; i < n; i++) {
        if (count[a[i]] > 0)
            cout << a[i];            // 输出重复元素
        count[a[i]]++;               // 记录 a[i] 出现的次数
    }
}

6. 逆置

逆置即将线性表反转，顺序完全反过来。

for (int i = 0; i < n/2; i++)
    swap(A[i], A[n-i-1]);

// 头插辅助函数
ListNode* Head_Insert(ListNode* L, ListNode* p) {
    ListNode* temp = p->next;        // 暂存 p 的下一个结点
    p->next = L->next;               // 先连后
    L->next = p;                     // 再连前
    return temp;                     // 返回 p 的下一个结点
}
void Reverse(ListNode* L) {          // 原地逆置
    ListNode* p = L->next;
    L->next = NULL;
    while (p != NULL)
        p = Head_Insert(L, p);       // 删 p，头插——重复此过程
}

3.1 考察结构

🌲 树和森林

typedef struct TNode{
    ElemType data;                  // 该结点的权值
    struct TNode *firstchild, *nextbro;   // firstchild 指向第一个孩子，nextbro 指向下一个兄弟
}TNode;

int father[MAX_SIZE];   // 保存每个结点的父亲结点下标

typedef struct TNode{
    ElemType data;             // 该结点的权值
    struct TNode *father;      // father 指向父结点
}TNode;

🌳 二叉树

typedef struct BTNode{
    ElemType data;                   // 该结点的权值
    struct BTNode *lchild, *rchild;  // lchild 指向左孩子，rchild 指向右孩子
}BTNode;

typedef struct{
    int SqBiTNode[MAX_SIZE];   // 一维数组保存二叉树结点
    int ElemNum;               // 结点个数
}SqBiTree;

3.2 树的递归遍历

二叉树的递归遍历

先、中、后序的递归遍历时间复杂度 O(n)，空间复杂度 O(h)（n 为总结点数，h 为树高）；若不确定树高，空间复杂度视为 O(n)。

void PreOrder(BTNode *p){
    if (p == NULL) return;
    visit(p);                // 先访问根
    PreOrder(p->lchild);
    PreOrder(p->rchild);
}

void InOrder(BTNode *p){
    if (p == NULL) return;
    InOrder(p->lchild);
    visit(p);                // 中间访问根
    InOrder(p->rchild);
}

void PostOrder(BTNode *p){
    if (p == NULL) return;
    PostOrder(p->lchild);
    PostOrder(p->rchild);
    visit(p);                // 最后访问根
}

树和森林的递归遍历

本质是对孩子兄弟表示法结构的递归操作，重点记住 「左孩子右兄弟」，可转化为"二叉树"模型来理解递归逻辑：

void TreePreOrder(TNode *T){
    if (T == NULL) return;
    visit(T);                     // 先访问根结点
    TreePreOrder(T->firstchild);  // 再遍历第一个孩子的整棵子树
    TreePreOrder(T->nextbro);     // 最后遍历下一个兄弟的子树
}

void TreePostOrder(TNode *T){
    if (T == NULL) return;
    TreePostOrder(T->firstchild);  // 先遍历第一个孩子的整棵子树
    visit(T);                      // 再访问根结点
    TreePostOrder(T->nextbro);     // 最后遍历下一个兄弟的子树
}

3.3 树的做题方法

408 中树算法考察的核心是树的遍历，因此应先确定选择哪种遍历方式，以对应遍历作为框架，把 visit(p) 改造成题目要求的功能。

📝 例题 4-1 ~ 4-6

int WPL = 0;                         // WPL 全局变量
void PreOrder(BTNode *p, int depth){ // 传入结点 p，附带深度 depth
    if (p == NULL) return;           // 空结点直接返回
    // visit(p);
    if (p->lchild == NULL && p->rchild == NULL)  // 叶结点
        WPL += depth * p->weight;    // 累加 深度×权值
    PreOrder(p->lchild, depth+1);    // 递归左子树
    PreOrder(p->rchild, depth+1);    // 递归右子树
}

int postOrder(BTNode *p, int depth){ // 传入结点 p，附带深度 depth
    if (p == NULL) return 0;         // 空结点返回 0
    int L_WPL = postOrder(p->lchild, depth+1);  // 左子树 WPL
    int R_WPL = postOrder(p->rchild, depth+1);  // 右子树 WPL
    // visit(p);
    if (p->lchild == NULL && p->rchild == NULL) // 叶结点
        return depth * p->weight;    // 返回 深度×权值
    else
        return L_WPL + R_WPL;        // 返回左右子树 WPL 之和
}

3.4 并查集

并查集是一种高效支持"集合合并"与"查找代表元"的数据结构，常用于处理图中连通性判断、集合合并问题，例如判断是否构成树、求连通块数量、判断环等。

常用双亲表示法定义：用数组 father[] 存储每个元素的"父结点"（其实是祖先结点），形成森林结构。通常将 father[] 定义成全局变量以方便使用。

int father[MAXN];            // father[i] 表示 i 的父结点（祖先）

// 查找根结点（含路径压缩）
int find(int x){
    if (father[x] != x)
        father[x] = find(father[x]);
    return father[x];
}

// 合并两个集合
void Union(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if (fx != fy)
        father[fy] = fx;   // 将 fy 的根指向 fx
}

typedef struct BTNode{
    int data;
    struct BTNode *lchild, *rchild;
}BTNode;

int ans(BTNode *T){
    BTNode* q[MAX_SIZE];           // 循环队列
    int front = 0, rear = 0, depth = 1;
    int last = 0;                  // 本层最后一个元素的下标
    if (T != NULL) q[rear++] = T;  // 根结点入队
    BTNode *p;                     // 当前出队结点
    int sum = 1 * 1;               // 初始化第一层的贡献：1 个结点 × 深度 1
    while (front < rear){
        p = q[front++];            // 出队
        if (p->lchild != NULL)
            q[rear++] = p->lchild;
        if (p->rchild != NULL)
            q[rear++] = p->rchild;
        if (front > last){        // 本层访问结束
            depth++;
            printf("%d %d %d\n", front, rear, depth);
            sum += (rear - front) * depth;  // 下一层的结点数 × 新深度
            last = rear - 1;       // 更新本层末尾哨兵
        }
    }
    return sum;
}

4.1 图的基本概念

若一个图中没有自环和重边，它被称为简单图，考试中的图默认简单图。

📖 基本术语

4.2 图的结构与遍历

📊 四种存储结构适用性

🔲 邻接矩阵

邻接矩阵常使用 0 表示不存在边，Edge[i][j] = 0 说明 i 到 j 之间不存在边。 无权图使用 1 表示边，有权图使用非 0 的数表示存在边。

邻接矩阵结构：

#define MAXV 100                    // 最大顶点数
typedef struct                      // 图的定义
{
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char verticesList[MAXV];        // 可选：每个顶点名称
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

邻接矩阵的遍历：

void TraverseEdges_MGraph(MGraph G)
{
    for (int i = 0; i < G.numVertices; i++)
        for (int j = 0; j < G.numVertices; j++)
            if (G.Edge[i][j] != 0)
                visit(i, j);        // 如果 i→j 存在边则处理
}

🔗 邻接表（类似孩子表示法）

邻接表结构：

#define MAXV 100                    // 最大顶点数

// 边结点
typedef struct ArcNode
{
    int adjvex;                     // 邻接点在顶点表中的下标
    struct ArcNode *next;           // 指向下一条边
    int weight;                     // 有权图可选：边权值
} ArcNode;

// 顶点结点
typedef struct VNode
{
    char data;                      // 可选：顶点信息
    ArcNode *first;                 // 指向第一条邻接边
} VNode;

// 邻接表图定义
typedef struct
{
    VNode verticesList[MAXV];       // 顶点表
    int numVertices, numEdges;      // 顶点数、边数
} ALGraph;

typedef struct ArcNode
{
    int adjvex;                     // 该弧所指向的顶点
    struct ArcNode *next;           // 指向下一条弧的指针
    int weight;                     // 有权图可选：边权值
} ArcNode;                          // 边结点

typedef struct
{
    ArcNode *verticesList[MAXV];    // 顶点数组
    int numVertices, arcnum;        // 图的当前顶点数和弧数
} ALGraph;

邻接表的遍历：

void TraverseEdges_ALGraph(ALGraph G)
{
    // 遍历所有顶点
    for (int i = 0; i < G.numVertices; i++)
    {
        // 遍历当前顶点 i 发出的所有边
        ArcNode *p = G.VerticesList[i].first;
        while (p != NULL)
        {
            visit(p);               // 访问对应边
            p = p->next;             // 处理下一条边
        }
    }
}

🔀 邻接多重表

邻接多重表结构：

#define MAXV 100

// 边结点
typedef struct EBox
{
    bool mark;                      // 标记是否访问
    int ivex, jvex;                 // 该边依附的两个顶点下标
    struct EBox *ilink, *jlink;     // 指向 ivex 和 jvex 的下一条边
    int weight;                     // 可选：边权值
} EBox;

// 顶点结点
typedef struct VexBox
{
    char data;                      // 顶点信息
    EBox *first;                    // 指向第一条边
} VexBox;

// 邻接多重表图定义
typedef struct
{
    VexBox VerticesList[MAXV];      // 顶点表
    int numVertices, numEdges;      // 顶点数、边数
} AMLGraph;

邻接多重表的遍历：

void TraverseEdges_AMLGraph(AMLGraph G)
{
    // 遍历所有顶点
    for (int i = 0; i < G.numVertices; i++)
    {
        // 遍历当前顶点 i 发出的所有边
        EBox *p = G.VerticesList[i].first;
        while (p != NULL)
        {
            if (p->mark != true)     // 如果未访问过则访问且标记
            {
                visit(p);
                p->mark = true;
            }
            if (i == p->ivex) p = p->ilink;
            else p = p->jlink;
        }
    }
}

✖️ 十字链表

十字链表结构：

#define MAXV 100

// 边结点
typedef struct ArcBox
{
    int tailvex, headvex;           // 弧尾（起点）和弧头（终点）在顶点表中的下标
    struct ArcBox *hlink;           // 指向同终点的下一条边（入边链）
    struct ArcBox *tlink;           // 指向同起点的下一条边（出边链）
    int weight;                     // 可选：边权值
} ArcBox;

// 顶点结点
typedef struct VexNode
{
    char data;                      // 顶点信息
    ArcBox *firstin, *firstout;     // 入边表、出边表指针
} VexNode;

// 十字链表图定义
typedef struct
{
    VexNode VerticesList[MAXV];     // 顶点表
    int numVertices, numEdges;      // 顶点数、边数
} OLGraph;

十字链表的遍历：

void TraverseEdges_OLGraph(OLGraph G)
{
    // 遍历所有顶点
    for (int i = 0; i < G.numVertices; i++)
    {
        // 遍历当前顶点 i 发出的所有边
        ArcBox *p = G.VerticesList[i].firstout;   // 请注意是出边
        while (p != NULL)
        {
            visit(p);               // 访问对应边
            p = p->tlink;            // 起点相同
        }
    }
}

4.3 图的经典算法

4.3.1 DFS（深度优先遍历）

📝 算法步骤（递归版）

1. 选择一个起始顶点 v，访问它，并标记为已访问（visited[v] = true）。
2. 查找 v 的所有邻接点 w。
3. 如果邻接点 w 未被访问，则从 w 开始进行 DFS（递归调用 DFS(G, w)）。
4. 如果 v 的所有邻接点都已被访问，则函数返回，实现回溯。

邻接表的 DFS 代码如下：

bool visited[MAXV] = {false};
void DFS_ALGraph(ALGraph G, int v)
{
    visit(v);                              // 访问顶点
    visited[v] = true;
    ArcNode *p = G.VerticesList[v].first;
    while (p != NULL)
    {
        if (!visited[p->adjvex])
            DFS_ALGraph(G, p->adjvex);
        p = p->next;
    }
}

void ans(ALGraph G)
{
    // 无向图调用 DFS 次数等于连通分量数
    for (i = 0; i < G.numVertices; i++)
        if (visited[i] != true) DFS_ALGraph(G, i);
}

若要改成邻接矩阵的 DFS 代码，就是把 void DFS_ALGraph(ALGraph G, int v) 中 while 循环改成 for 循环。

4.3.2 BFS（广度优先遍历）

📝 算法步骤

1. 选择一个起始（蓝色）顶点 v，将其加入队列，标记为已入队（蓝 → 橙）。
2. 当队列不为空时，循环执行以下操作：
   a. 从队头取出一个顶点 u，访问该结点；
   b. 遍历 u 的所有邻接点 w：若 w 未入队，则访问 w，并将其加入队列，标记为已入队（蓝 → 橙）。遍历完后 u 由橙 → 绿。

邻接表的 BFS 遍历：

bool visited[MAXV] = {false};               // 表示顶点是否已入队
void BFS_ALGraph(ALGraph G, int v)
{
    int queue[MAXV], front = 0, rear = 0;

    // 1.将 v 入队，标记
    queue[rear++] = v;
    visited[v] = true;

    // 2.如果队列不为空则循环
    while (front < rear)
    {
        // 2-a.选择队头元素 u 访问
        int u = queue[front++];
        visit(u);

        // 2-b.将 u 出发可到达的所有未访问顶点加入队列
        ArcNode *p = G.VerticesList[u].first;
        while (p != NULL)
        {
            if (visited[p->adjvex] != true)
            {
                queue[rear++] = p->adjvex;
                visited[p->adjvex] = true;
            }
            p = p->next;
        }
    }
}

void ans(ALGraph G)
{
    // 无向图调用 BFS 次数等于连通分量数
    for (i = 0; i < G.numVertices; i++)
        if (visited[i] != true) BFS_ALGraph(G, i);
}

📋 DFS 与 BFS 对比

4.3.3 单源最短路径

🟢 无权图

对无权图（或是权值相同的图）来说，最短路径是指从一个顶点到另一个顶点经过的边数最少的路径。 我们可以用 BFS 来寻找最短路径，因为 BFS 按层级遍历图，天然地保证了最先到达某个顶点的路径就是最短路径。

📝 步骤

1. 初始化距离数组 dist，dist[start] = 0，所有其他顶点的距离为无穷大 ∞。同时，初始化路径数组 path 用于记录前驱结点。
2. 创建一个队列，并将源点 start 入队。
3. 队列不为空则循环执行：
   a. 从队头取出一个顶点 u。
   b. 遍历 u 的所有邻接点 v；若 v 尚未入队则将 v 入队并更新距离。

邻接表代码如下，时间复杂度为 O(n+e)：

// 使用BFS计算无权图的单源最短路径
void BFS_ShortestPath_AL(ALGraph G, int start)
{
    int queue[MAXV];
    int dist[MAXV], path[MAXV];
    int front = 0, rear = 0;

    // 1.初始化
    for (int i = 0; i < G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }

    // 2.将源点入队
    dist[start] = 0;
    queue[rear++] = start;              // 源点入队

    // 3.当队列不为空时，循环执行
    while (front < rear)                // 队列不为空
    {
        // 3-a.队头元素 u 出队
        int u = queue[front++];         // 队头元素出队

        // 3-b.遍历 u 的所有相邻结点 v，如果 v 尚未入队过则将 v 入队并更新距离
        p = G.VerticesList[u].first;
        while (p != NULL)
        {
            int v = p->adjvex;          // 获取邻接点 v 的下标
            // 如果 v 尚未被访问过
            if (dist[v] == INT_MAX)
            {
                dist[v] = dist[u] + 1;  // v 的距离是 u 的距离 +1
                path[v] = u;            // v 的前驱是 u
                queue[rear++] = v;      // 将新访问的顶点 v 入队
            }
            p = p->next;
        }
    }
    // 根据 dist 数组输出长度，根据 path 数组输出路径
}

🔵 有权图 —— Dijkstra 算法

这个算法的精髓（贪心策略）在于：每次都选择当前看起来最近的那个点，并认定它的最短路径已经找到，然后用它来更新其他邻居点的路径。

📝 步骤

1. 初始化。初始化距离数组 dist，dist[s] = 0，所有其他顶点的距离为无穷大 ∞。同时，初始化路径数组 path 用于记录前驱结点。
2. 循环直到所有顶点都已确定：
   a. 每次选择距离 dist 最小的、未选择过已确定顶点 u。
   b. 将顶点 u 视为已确定的顶点，之后不再考虑。
   c. 将 u 出发的所有邻接点 v 做松弛：

if (dist[u] + w(u, v) < dist[v])
    dist[v] = dist[u] + w(u, v)

4.3.4 最小生成树

有两种算法：Prim 算法和 Kruskal 算法。

🌱 Prim 算法（从顶点的角度出发）

🌿 Kruskal 算法（从边的角度出发）

⚖️ Prim 与 Dijkstra 的比较

📌 习题 5-4（Kruskal 综合题）

typedef struct ArcNode
{
    int ivex;                       // 该弧起始的顶点
    int jvex;                       // 该弧所指向的顶点
    struct ArcNode *nextarc;        // 指向下一条弧的指针
    int weight;                     // 边权值
} ArcNode;                          // 边结点

typedef struct
{
    int data;                       // 顶点信息
    ArcNode *firstarc;              // 指向第一条依附该顶点的弧的指针
} VNode;                            // 顶点结点

typedef struct
{
    VNode VerticesList[MAXV];       // 顶点数组
    int numVertices, arcnum;        // 图的当前顶点数和弧数
} ALGraph;

✅ 参考答案

（3）算法实现：

int father[MAXV];                       // 用于并查集的表示

int Find(int x){                        // 查找根结点
    if (father[x] != x){
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y){               // 合并两棵树
    int fx = Find(x);
    int fy = Find(y);
    if (fx != fy){
        father[fy] = fx;
    }
}

int MSTWeight(ALGraph G){
    int count = 0;                      // 统计查找次数
    int totalweight = 0;
    for (int i = 0; i < G.numVertices; i++){   // 初始化并查集，初始时所有顶点属于不同集合
        father[i] = i;
    }
    while (count < (G.numVertices - 1)){       // n 个顶点的最小生成树最多有 n-1 条边
        ArcNode *p = FindEdge();        // 通过 FindEdge() 得到最小边
        int rootu = Find(p->ivex);      // 对还未处理的最小边，判断其两个顶点是否在不同的集合里
        int rootv = Find(p->jvex);
        if (rootu != rootv){            // 若在不同集合中，则选择该边，并合并两个顶点所在的集合
            Union(rootu, rootv);
            count++;
            totalweight += p->weight;
        }
    }
    return totalweight;
}

4.3.5 拓扑排序

📋 拓扑序列的三种情况

📝 步骤

1. 统计每个顶点的入度。
2. 将入度为 0 的顶点入队。
3. 队列出队一个顶点，访问它，并将它的出边所指向顶点的入度减 1。
4. 若减到 0，再次入队。
5. 队列为空，排序完成；若有未访问顶点，存在环。

邻接表的代码，时间复杂度为 O(n+e)：

void TopoSort(ALGraph G)
{
    int indegree[MAXV] = {0};

    // 计算每个顶点的入度
    for (int i = 0; i < G.numVertices; i++)
    {
        ArcNode *p = G.VerticesList[i].first;
        while (p != NULL)
        {
            indegree[p->adjvex]++;
            p = p->next;
        }
    }

    // 将所有入度为 0 的顶点入队
    int queue[MAXV], front = 0, rear = 0;
    for (int i = 0; i < G.numVertices; i++)
        if (indegree[i] == 0)
            queue[rear++] = i;

    while (front < rear)
    {
        int u = queue[front++];
        输出顶点 u

        // 此处可判断是否只有一个顶点可选，即 front+1 == rear

        for (ArcNode *p = G.VerticesList[u].first; p != NULL; p = p->next)
        {
            int v = p->adjvex;
            if (--indegree[v] == 0)
                queue[rear++] = v;
        }
    }

    if (rear < G.numVertices)
        拓扑序列不存在，该有向图存在环
}

🔍 拓扑排序流程对照

草稿纸上列出流程 → 根据流程在试卷上分块还原代码：

4.3.6 * 关键路径