第5章图算法

旧版讲义 · 校订增强 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第5章图算法¶

图的存储结构：先确定怎样枚举邻接点¶

邻接矩阵与邻接表应怎样按稠密程度选择？¶

何时用：图算法落笔前，需要决定边是否存在、枚举邻接点和复杂度口径。

思路步骤：

邻接矩阵 edge[u][v] 适合稠密图，查边 O(1)，枚举一个顶点邻接点 O(n)。
邻接表只存实际边，枚举 u 的出边与 outdegree(u) 成正比。
无向邻接表通常每条边存两次；复杂度仍记 O(n+e)。
有权图若用 0 表示无边，就不能同时表示合法 0 权边；应另设 INF/has_edge。

伪代码/关键模板：

typedef struct ACArc {
    int to;
    int weight;
    struct ACArc *next;
} ACArc;

typedef struct ACAdjGraph {
    ACArc *head[AC_MAXV];
    int n;
    int m;
    int directed;
} ACAdjGraph;

typedef struct ACMatrixGraph {
    int n;
    int m;
    int edge[AC_MAXV][AC_MAXV];
} ACMatrixGraph;

复杂度：矩阵空间 O(n²)，邻接表空间 O(n+e)；矩阵遍历全部边 O(n²)，邻接表 O(n+e)。

易错边界：新版补充/校订：旧版用 0 同时表示无边，因此其 Dijkstra/Prim 模板不支持 0 权边；若题目允许 0 权边，必须分离“是否有边”和“边权”。

回源 · PDF 第 134 页 · b_134_6；PDF 第 134 页 · b_134_7；PDF 第 135 页 · b_135_0；PDF 第 135 页 · b_135_2；PDF 第 135 页 · b_135_3；PDF 第 135 页 · b_135_5；PDF 第 135 页 · b_135_8；PDF 第 136 页 · b_136_0；PDF 第 136 页 · b_136_4；PDF 第 136 页 · b_136_8

邻接表遍历为何最容易错在 while 的花括号？¶

何时用：统计出度、扫描所有边、DFS/BFS 扩展邻接点。

思路步骤：

外层枚举顶点 u。
p 从 head[u] 开始。
while 内访问当前边，再执行 p=p->next。
无向图每条逻辑边会出现两次；是否除以 2 取决于统计目标。

伪代码/关键模板：

void ac_for_each_arc(
    const ACAdjGraph *g, void (*visit)(int from, int to, int weight)
) {
    if (g == NULL || visit == NULL) return;
    for (int u = 0; u < g->n; ++u) {
        for (const ACArc *p = g->head[u]; p != NULL; p = p->next) {
            visit(u, p->to, p->weight);
        }
    }
}

复杂度：有向图 O(n+e)；无向邻接表存两份边，仍是 O(n+e)。

易错边界：旧版 OCR/排版常把 while 后语句挤出花括号，实际代码必须把 visit 与推进都放在循环体；若漏推进会死循环。

回源 · PDF 第 136 页 · b_136_10；PDF 第 136 页 · b_136_11；PDF 第 136 页 · b_136_13；PDF 第 136 页 · b_136_14

邻接多重表为什么适合无向图“一条边只存一次”？¶

何时用：无向图需要直接修改/标记边，或从任一端点沿其关联边链遍历。

思路步骤：

每条边结点记录两个端点 ivex、jvex。
ilink 串起依附于 ivex 的下一条边，jlink 串起依附于 jvex 的下一条边。
从顶点 k 遍历时，若 k==ivex 就走 ilink，否则走 jlink。
mark 可保证全图遍历时每条无向边只处理一次。

伪代码/关键模板：

typedef struct ACMLEdge {
    int mark;
    int ivex;
    int jvex;
    struct ACMLEdge *ilink;
    struct ACMLEdge *jlink;
    int weight;
} ACMLEdge;

typedef struct ACMLGraph {
    ACMLEdge *first[AC_MAXV];
    int n;
    int m;
} ACMLGraph;

复杂度：空间 O(n+e)；从顶点 k 扫描其关联边 O(degree(k))。

易错边界：当前顶点决定走 ilink 还是 jlink；不能固定走一个链域；遍历全图时 mark 的初始化和所有权要明确。

回源 · PDF 第 137 页 · b_137_0；PDF 第 137 页 · b_137_4；PDF 第 137 页 · b_137_5；PDF 第 137 页 · b_137_6；PDF 第 137 页 · b_137_10；PDF 第 137 页 · b_137_12；PDF 第 138 页 · b_138_0；PDF 第 138 页 · b_138_1

十字链表怎样分别沿入边链与出边链？¶

何时用：有向图需要同时快速取得某顶点全部入边和全部出边。

思路步骤：

边结点保存 tail（弧尾）与 head（弧头）。
tlink 连接“同一弧尾”的下一条出边。
hlink 连接“同一弧头”的下一条入边。
顶点结点分别保存 first_out 与 first_in。

伪代码/关键模板：

typedef struct ACArcBox {
    int tail;
    int head;
    int weight;
    struct ACArcBox *hlink;
    struct ACArcBox *tlink;
} ACArcBox;

typedef struct ACOLGraph {
    ACArcBox *first_in[AC_MAXV];
    ACArcBox *first_out[AC_MAXV];
    int n;
    int m;
} ACOLGraph;

复杂度：空间 O(n+e)；枚举某顶点出边 O(outdegree)，入边 O(indegree)。

易错边界：出边链必须沿 tlink，入边链沿 hlink；邻接多重表面向无向图，十字链表面向有向图，不能只凭字段相似混用。

回源 · PDF 第 138 页 · b_138_2；PDF 第 138 页 · b_138_7；PDF 第 138 页 · b_138_10；PDF 第 138 页 · b_138_12；PDF 第 139 页 · b_139_0；PDF 第 139 页 · b_139_3；PDF 第 139 页 · b_139_5；PDF 第 139 页 · b_139_6

DFS、BFS 与连通性¶

DFS 为什么要把 visited 状态贯穿整片森林？¶

何时用：图的深度优先遍历、路径搜索、连通分量和环检测。

思路步骤：

进入顶点 v 立即标记已访问。
扫描 v 的每个邻接点 w。
w 未访问则递归 DFS(w)。
若图可能不连通，外层再扫描所有顶点，对每个未访问点启动新一轮 DFS。

伪代码/关键模板：

void ac_dfs_component(
    const ACAdjGraph *g, int v, unsigned char seen[],
    void (*visit)(int)
) {
    seen[v] = 1;
    if (visit != NULL) visit(v);
    for (const ACArc *p = g->head[v]; p != NULL; p = p->next) {
        int w = p->to;
        if (w >= 0 && w < g->n && !seen[w]) {
            ac_dfs_component(g, w, seen, visit);
        }
    }
}

复杂度：邻接表 O(n+e)，邻接矩阵 O(n²)；递归栈最坏 O(n)。

易错边界：只从 0 号点 DFS 只能覆盖其连通分量；visited 应在整次森林遍历前统一清零，不能每次递归清零。

回源 · PDF 第 139 页 · b_139_10；PDF 第 139 页 · b_139_11；PDF 第 139 页 · b_139_13；PDF 第 139 页 · b_139_14；PDF 第 140 页 · b_140_0；PDF 第 140 页 · b_140_1；PDF 第 140 页 · b_140_2；PDF 第 140 页 · b_140_4；PDF 第 140 页 · b_140_5；PDF 第 140 页 · b_140_6

BFS 为什么必须在入队时标记，而不是出队时？¶

何时用：层次遍历、无权最短路、二分图染色和连通性判断。

思路步骤：

起点入队并立即 seen=true。
队头出队后访问。
每个未见邻接点在第一次发现时标记并入队。
入队即标记可防止同一顶点被多个前驱重复加入队列。

伪代码/关键模板：

int ac_bfs_component(
    const ACAdjGraph *g, int start, unsigned char seen[],
    void (*visit)(int)
) {
    if (g == NULL || start < 0 || start >= g->n) return 0;
    int queue[AC_MAXV], front = 0, rear = 0;
    queue[rear++] = start;
    seen[start] = 1;
    while (front < rear) {
        int u = queue[front++];
        if (visit != NULL) visit(u);
        for (const ACArc *p = g->head[u]; p != NULL; p = p->next) {
            int v = p->to;
            if (v >= 0 && v < g->n && !seen[v]) {
                if (rear >= AC_MAXV) return 0;
                seen[v] = 1;
                queue[rear++] = v;
            }
        }
    }
    return 1;
}

复杂度：邻接表 O(n+e)，额外队列与标记 O(n)。

易错边界：出队才标记会导致重复入队甚至队列溢出；遍历次序依邻接表顺序而异，但层数/最短距离不受影响。

回源 · PDF 第 141 页 · b_141_0；PDF 第 141 页 · b_141_1；PDF 第 141 页 · b_141_2；PDF 第 141 页 · b_141_5；PDF 第 141 页 · b_141_6；PDF 第 141 页 · b_141_7；PDF 第 141 页 · b_141_8；PDF 第 141 页 · b_141_10；PDF 第 142 页 · b_142_1；PDF 第 142 页 · b_142_2

连通性与连通分量数为什么只是“启动几次遍历”？¶

何时用：无向图判断连通、统计连通分量。

思路步骤：

seen 全部置 0。
依次扫描顶点 i。
若 i 未访问，说明发现新分量，count++ 并 DFS/BFS 覆盖它。
非空无向图连通当且仅当最终 count==1。

伪代码/关键模板：

int ac_count_components(const ACAdjGraph *g) {
    if (g == NULL || g->n < 0 || g->n > AC_MAXV) return -1;
    unsigned char seen[AC_MAXV] = {0};
    int count = 0;
    for (int i = 0; i < g->n; ++i) {
        if (!seen[i]) {
            ++count;
            ac_dfs_component(g, i, seen, NULL);
        }
    }
    return count;
}

int ac_is_connected(const ACAdjGraph *g) {
    int count = ac_count_components(g);
    return count == 0 || count == 1;
}

复杂度：邻接表 O(n+e)，标记与递归栈 O(n)。

易错边界：空图是否称连通要按题目定义，本卡把 0/1 个顶点视为无需分割；有向图需区分弱连通与强连通，不能直接套无向图结论。

回源 · PDF 第 170 页 · b_170_1；PDF 第 170 页 · b_170_2；PDF 第 170 页 · b_170_3；PDF 第 170 页 · b_170_4；PDF 第 170 页 · b_170_5；PDF 第 170 页 · b_170_7；PDF 第 170 页 · b_170_8；PDF 第 170 页 · b_170_9；PDF 第 170 页 · b_170_10；PDF 第 171 页 · b_171_0；PDF 第 171 页 · b_171_1

无向图 DFS 判环，为什么“见过邻点”还不够？¶

何时用：简单无向图采用邻接表，判断任意连通分量是否含环。

思路步骤：

DFS(v,parent)，先标记 v。
未访问邻点 w 就递归 DFS(w,v)。
已访问邻点若 w!=parent，说明出现返祖/交叉到已在生成树中的顶点，存在环。
外层从每个未访问顶点启动，覆盖非连通图。

伪代码/关键模板：

int ac_cycle_dfs(
    const ACAdjGraph *g, int v, int parent, unsigned char seen[]
) {
    seen[v] = 1;
    for (const ACArc *p = g->head[v]; p != NULL; p = p->next) {
        int w = p->to;
        if (w < 0 || w >= g->n) continue;
        if (!seen[w]) {
            if (ac_cycle_dfs(g, w, v, seen)) return 1;
        } else if (w != parent) {
            return 1;
        }
    }
    return 0;
}

int ac_has_undirected_cycle(const ACAdjGraph *g) {
    if (g == NULL || g->n < 0 || g->n > AC_MAXV) return 0;
    unsigned char seen[AC_MAXV] = {0};
    for (int v = 0; v < g->n; ++v) {
        if (!seen[v] && ac_cycle_dfs(g, v, -1, seen)) return 1;
    }
    return 0;
}

复杂度：时间 O(n+e)，空间 O(n)。

易错边界：新版补充/校订：遇到已访问邻点不能直接判环，因为无向边会反向看到父结点；必须排除 parent。该写法假设简单图，多重边需记录父边编号而非只记父顶点。

回源 · PDF 第 165 页 · b_165_10；PDF 第 165 页 · b_165_11；PDF 第 166 页 · b_166_0；PDF 第 166 页 · b_166_1；PDF 第 166 页 · b_166_2；PDF 第 166 页 · b_166_3；PDF 第 166 页 · b_166_4；PDF 第 166 页 · b_166_5；PDF 第 166 页 · b_166_6；PDF 第 166 页 · b_166_7；PDF 第 167 页 · b_167_0

二分图染色为什么要从每个未染色顶点重新启动？¶

何时用：无向图判断能否二染色，图可能不连通。

思路步骤：

color=0 表示未染色，1/-1 表示两组。
对每个未染色顶点启动 BFS 并染为 1。
未染色邻点染成相反颜色并入队。
若某条边两端颜色相同，立即失败。
所有分量完成则为二分图。

伪代码/关键模板：

int ac_is_bipartite_matrix(const ACMatrixGraph *g) {
    if (g == NULL || g->n < 0 || g->n > AC_MAXV) return 0;
    signed char color[AC_MAXV] = {0};
    int queue[AC_MAXV];
    for (int start = 0; start < g->n; ++start) {
        if (color[start] != 0) continue;
        int front = 0, rear = 0;
        color[start] = 1;
        queue[rear++] = start;
        while (front < rear) {
            int u = queue[front++];
            for (int v = 0; v < g->n; ++v) {
                if (g->edge[u][v] == 0) continue;
                if (color[v] == color[u]) return 0;
                if (color[v] == 0) {
                    color[v] = (signed char)-color[u];
                    queue[rear++] = v;
                }
            }
        }
    }
    return 1;
}

复杂度：邻接矩阵 O(n²)，颜色和队列 O(n)。

易错边界：只从 0 号顶点染色会漏掉其他分量中的奇环。新版补充/校订：二分图本质是“无奇环”，不是旧版解析中误写的“判断是否存在偶数环”。

回源 · PDF 第 169 页 · b_169_0；PDF 第 169 页 · b_169_1；PDF 第 169 页 · b_169_2；PDF 第 169 页 · b_169_5；PDF 第 169 页 · b_169_6；PDF 第 169 页 · b_169_7；PDF 第 169 页 · b_169_8；PDF 第 169 页 · b_169_9；PDF 第 169 页 · b_169_10；PDF 第 169 页 · b_169_11；PDF 第 169 页 · b_169_12；PDF 第 170 页 · b_170_0

单源最短路径¶

无权图最短路，dist 为什么可以兼任 visited？¶

何时用：无权图或所有边权相同，求源点到各顶点最少边数及前驱。

思路步骤：

dist 全设 -1，prev 全设 -1。
源点 dist=0 并入队。
扫描 u 的邻点 v；仅当 dist[v]==-1 时首次发现。
设置 dist[v]=dist[u]+1、prev[v]=u 并入队。
结束后 dist=-1 的顶点不可达。

伪代码/关键模板：

int ac_unweighted_shortest(
    const ACAdjGraph *g, int start, int dist[], int previous[]
) {
    if (g == NULL || dist == NULL || previous == NULL
        || start < 0 || start >= g->n || g->n > AC_MAXV) return 0;
    int queue[AC_MAXV], front = 0, rear = 0;
    for (int i = 0; i < g->n; ++i) {
        dist[i] = -1;
        previous[i] = -1;
    }
    dist[start] = 0;
    queue[rear++] = start;
    while (front < rear) {
        int u = queue[front++];
        for (const ACArc *p = g->head[u]; p != NULL; p = p->next) {
            int v = p->to;
            if (v >= 0 && v < g->n && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                previous[v] = u;
                queue[rear++] = v;
            }
        }
    }
    return 1;
}

复杂度：邻接表 O(n+e)，空间 O(n)。

易错边界：只有第一次发现才写前驱；边权不全相同则不能用普通 BFS；回溯路径时从终点沿 previous 逆向到源点。

回源 · PDF 第 143 页 · b_143_0；PDF 第 143 页 · b_143_1；PDF 第 143 页 · b_143_2；PDF 第 143 页 · b_143_3；PDF 第 143 页 · b_143_5；PDF 第 143 页 · b_143_6；PDF 第 143 页 · b_143_7；PDF 第 144 页 · b_144_1；PDF 第 144 页 · b_144_2；PDF 第 144 页 · b_144_3；PDF 第 144 页 · b_144_4；PDF 第 144 页 · b_144_7

Dijkstra 怎样把非负权、无穷大和非连通图写完整？¶

何时用：边权非负的有向或无向图，求单源最短路径。

思路步骤：

dist[start]=0，其余为 INF；done 全 false。
每轮选择未确定且 dist 最小的 u。
若不存在这样的 u，剩余顶点不可达，正常结束而非判算法失败。
将 u 标记确定，再对每条 u→v 做松弛。
负权边必须拒绝；加法使用 long long 并避免 INF 参与运算。

伪代码/关键模板：

int ac_dijkstra_matrix(
    const ACMatrixGraph *g, int start, long long dist[], int previous[]
) {
    if (g == NULL || dist == NULL || previous == NULL
        || start < 0 || start >= g->n || g->n > AC_MAXV) return 0;
    const long long inf = 9223372036854775807LL / 4;
    unsigned char done[AC_MAXV] = {0};
    for (int u = 0; u < g->n; ++u) {
        dist[u] = inf;
        previous[u] = -1;
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] < 0) return 0;
        }
    }
    dist[start] = 0;
    for (int step = 0; step < g->n; ++step) {
        int u = -1;
        for (int v = 0; v < g->n; ++v) {
            if (!done[v] && dist[v] < inf && (u < 0 || dist[v] < dist[u])) u = v;
        }
        if (u < 0) break;
        done[u] = 1;
        for (int v = 0; v < g->n; ++v) {
            int weight = g->edge[u][v];
            if (!done[v] && weight != 0 && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                previous[v] = u;
            }
        }
    }
    return 1;
}

复杂度：邻接矩阵实现 O(n²)、空间 O(n)；邻接表加二叉堆为 O((n+e)log n)。

易错边界：Dijkstra 不支持负权。新版边界说明：若题设保证图连通，旧版不会遇到“选不到 u”；一般图中则应保留不可达顶点为 INF，而不是把算法整体判错。旧版 int 加法也可能溢出。本模板仍沿用 0=无边，因此不支持 0 权边。

回源 · PDF 第 145 页 · b_145_1；PDF 第 145 页 · b_145_2；PDF 第 145 页 · b_145_9；PDF 第 146 页 · b_146_1；PDF 第 146 页 · b_146_2；PDF 第 146 页 · b_146_4；PDF 第 146 页 · b_146_6；PDF 第 146 页 · b_146_7；PDF 第 146 页 · b_146_8；PDF 第 146 页 · b_146_9；PDF 第 147 页 · b_147_0；PDF 第 147 页 · b_147_1；PDF 第 147 页 · b_147_2；PDF 第 148 页 · b_148_0；PDF 第 148 页 · b_148_1

最小生成树：Prim 选点，Kruskal 选边¶

Prim 的 cost 与 Dijkstra 的 dist 有什么本质区别？¶

何时用：连通无向带权图求最小生成树，尤其适合邻接矩阵或稠密图。

思路步骤：

selected 初始为空，best[start]=0。
每轮选未加入且 best 最小的顶点 u。
把 u 加入生成树，累加 best[u]。
用边权 w(u,v) 更新未选顶点 v 到“已选集合”的最小连接代价。
选不到顶点说明图不连通，不存在覆盖全部顶点的生成树。

伪代码/关键模板：

int ac_prim_matrix(
    const ACMatrixGraph *g, long long *total, int parent[]
) {
    if (g == NULL || total == NULL || parent == NULL
        || g->n <= 0 || g->n > AC_MAXV) return 0;
    const long long inf = 9223372036854775807LL / 4;
    long long best[AC_MAXV];
    unsigned char selected[AC_MAXV] = {0};
    for (int i = 0; i < g->n; ++i) {
        best[i] = inf;
        parent[i] = -1;
    }
    best[0] = 0;
    long long sum = 0;
    for (int step = 0; step < g->n; ++step) {
        int u = -1;
        for (int v = 0; v < g->n; ++v) {
            if (!selected[v] && (u < 0 || best[v] < best[u])) u = v;
        }
        if (u < 0 || best[u] == inf) return 0;
        selected[u] = 1;
        sum += best[u];
        for (int v = 0; v < g->n; ++v) {
            int weight = g->edge[u][v];
            if (!selected[v] && weight != 0 && weight < best[v]) {
                best[v] = weight;
                parent[v] = u;
            }
        }
    }
    *total = sum;
    return 1;
}

复杂度：邻接矩阵 O(n²)、空间 O(n)；堆优化邻接表为 O((n+e)log n)。

易错边界：Prim 的 best 是“到已选集合的一条边”，Dijkstra 的 dist 是“到源点的一条路径”；本模板允许负权但仍因 0=无边而不支持 0 权边。

回源 · PDF 第 149 页 · b_149_0；PDF 第 149 页 · b_149_1；PDF 第 149 页 · b_149_2；PDF 第 149 页 · b_149_3；PDF 第 149 页 · b_149_4；PDF 第 149 页 · b_149_5；PDF 第 149 页 · b_149_6；PDF 第 149 页 · b_149_7；PDF 第 149 页 · b_149_8；PDF 第 149 页 · b_149_9；PDF 第 149 页 · b_149_10；PDF 第 150 页 · b_150_1；PDF 第 150 页 · b_150_2；PDF 第 151 页 · b_151_1；PDF 第 151 页 · b_151_2；PDF 第 151 页 · b_151_3

Kruskal 为什么用并查集判断“加入这条边是否成环”？¶

何时用：无向带权图以边集给出，或稀疏图适合按边权排序。

思路步骤：

边按权值非降序排列。
每个顶点初始化为独立集合。
依次检查边 (u,v)：若两端代表元相同，加入会成环，跳过。
否则合并集合、选中该边并累加权值。
选满 n-1 条成功；边耗尽仍不足则图不连通。

伪代码/关键模板：

typedef struct ACEdge {
    int u;
    int v;
    int weight;
} ACEdge;

int ac_kruskal_sorted(
    int n, const ACEdge edges[], int m, long long *total
) {
    if (n <= 0 || n > AC_MAXV || edges == NULL || total == NULL || m < 0) return 0;
    ACDSU dsu;
    ac_dsu_init(&dsu, n);
    int chosen = 0;
    long long sum = 0;
    for (int i = 0; i < m && chosen < n - 1; ++i) {
        int u = edges[i].u, v = edges[i].v;
        if (u < 0 || u >= n || v < 0 || v >= n) return 0;
        if (ac_dsu_union(&dsu, u, v)) {
            sum += edges[i].weight;
            ++chosen;
        }
    }
    if (chosen != n - 1) return 0;
    *total = sum;
    return 1;
}

复杂度：排序 O(e log e)，并查集合计 O(eα(n))，总时间 O(e log e)，空间 O(n+e)（含边集）。

易错边界：函数前提是 edges 已排序；不能只取前 n-1 条最小边而不判环；不连通图得到的是最小生成森林，不是生成树。

回源 · PDF 第 151 页 · b_151_4；PDF 第 151 页 · b_151_5；PDF 第 151 页 · b_151_6；PDF 第 151 页 · b_151_7；PDF 第 151 页 · b_151_8；PDF 第 151 页 · b_151_9；PDF 第 151 页 · b_151_10；PDF 第 151 页 · b_151_12；PDF 第 151 页 · b_151_13；PDF 第 151 页 · b_151_14；PDF 第 151 页 · b_151_17；PDF 第 152 页 · b_152_0；PDF 第 152 页 · b_152_1

拓扑排序与关键路径¶

Kahn 拓扑排序怎样同时判断“存在”和“有环”？¶

何时用：有向图寻找拓扑序列或判断是否为 DAG。

思路步骤：

统计每个顶点入度。
所有入度为 0 的顶点入队。
反复出队 u，写入序列，并把 u 的每条出边终点入度减一。
新变为 0 的顶点入队。
最终输出数等于 n 则存在拓扑序；否则剩余顶点位于环内或依赖环。

伪代码/关键模板：

int ac_toposort_matrix(const ACMatrixGraph *g, int order[]) {
    if (g == NULL || order == NULL || g->n < 0 || g->n > AC_MAXV) return 0;
    int indegree[AC_MAXV] = {0};
    int queue[AC_MAXV], front = 0, rear = 0, count = 0;
    for (int u = 0; u < g->n; ++u) {
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] != 0) ++indegree[v];
        }
    }
    for (int v = 0; v < g->n; ++v) {
        if (indegree[v] == 0) queue[rear++] = v;
    }
    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] != 0 && --indegree[v] == 0) {
                queue[rear++] = v;
            }
        }
    }
    return count == g->n;
}

复杂度：邻接矩阵 O(n²)，邻接表 O(n+e)，辅助空间 O(n)。

易错边界：有多个零入度顶点不代表不存在拓扑序，只代表当前选择不唯一；只有最终处理数<n 才说明有环。

回源 · PDF 第 153 页 · b_153_0；PDF 第 153 页 · b_153_2；PDF 第 153 页 · b_153_3；PDF 第 153 页 · b_153_4；PDF 第 153 页 · b_153_5；PDF 第 153 页 · b_153_6；PDF 第 153 页 · b_153_7；PDF 第 153 页 · b_153_8；PDF 第 153 页 · b_153_9；PDF 第 153 页 · b_153_10；PDF 第 154 页 · b_154_0；PDF 第 154 页 · b_154_1；PDF 第 154 页 · b_154_2；PDF 第 154 页 · b_154_4；PDF 第 154 页 · b_154_6；PDF 第 155 页 · b_155_0；PDF 第 155 页 · b_155_1

AOE 网关键路径，ve、vl 与活动松弛顺序怎样记？¶

何时用：带权 DAG 的活动在边上，求工程最短完成时间与关键活动。

思路步骤：

拓扑排序；若处理顶点数不足 n，存在环，关键路径无定义。
按拓扑序正向计算 ve[v]=max(ve[u]+w(u,v))。
工期 duration 应取所有汇点 ve 的最大值，或先补一个超级汇点。
vl 全初始化为 duration，按逆拓扑序计算 vl[u]=min(vl[v]-w(u,v))。
边 (u,v) 的最早开始 e=ve[u]，最迟开始 l=vl[v]-w；e==l 即关键活动。

伪代码/关键模板：

topological_order()
for u in topo:
    for (u,v,w): ve[v] = max(ve[v], ve[u] + w)
duration = max(ve[sink])
vl[*] = duration
for u in reverse(topo):
    for (u,v,w): vl[u] = min(vl[u], vl[v] - w)
critical(u,v) ⇔ ve[u] == vl[v] - w

复杂度：邻接表 O(n+e)，数组与拓扑序空间 O(n)。

易错边界：新版边界说明：旧版用 ve[n-1] 初始化 vl，适用于题设保证唯一汇点编号为 n-1 的模型；一般编号或多汇点情形应取汇点最大 ve，或先加超级汇点。关键路径可能不唯一。

回源 · PDF 第 155 页 · b_155_2；PDF 第 155 页 · b_155_4；PDF 第 155 页 · b_155_5；PDF 第 155 页 · b_155_6；PDF 第 155 页 · b_155_7；PDF 第 155 页 · b_155_8；PDF 第 155 页 · b_155_9；PDF 第 156 页 · b_156_0；PDF 第 156 页 · b_156_1；PDF 第 156 页 · b_156_2；PDF 第 156 页 · b_156_4；PDF 第 156 页 · b_156_6；PDF 第 156 页 · b_156_7；PDF 第 157 页 · b_157_0；PDF 第 157 页 · b_157_1

特殊结构与度数统计¶

邻接表、矩阵与邻接多重表中，“度”分别怎样数？¶

何时用：统计有向图入/出度、无向图顶点度，或在邻接多重表中求指定顶点度。

思路步骤：

有向邻接矩阵：第 u 行非零数是出度，第 u 列非零数是入度。
有向邻接表：u 的边链长度是出度；入度需扫描全部边或另存逆邻接表。
无向邻接表：u 的链长就是度，但每条边在全图总计两次。
邻接多重表从 first[k] 开始，每经过一条边度加一，再按 k 位于哪一端选择下一链域。

伪代码/关键模板：

int ac_aml_degree(const ACMLGraph *g, int k) {
    if (g == NULL || k < 0 || k >= g->n) return -1;
    int degree = 0;
    const ACMLEdge *p = g->first[k];
    while (p != NULL) {
        ++degree;
        if (p->ivex == k) p = p->ilink;
        else if (p->jvex == k) p = p->jlink;
        else return -1;
    }
    return degree;
}

复杂度：矩阵单点入/出度 O(n)；邻接表出度和邻接多重表度 O(degree)。

易错边界：自环在无向图度数中贡献 2，但本讲默认简单图无自环；邻接多重表每条边只存一次，不能再除以 2。

回源 · PDF 第 172 页 · b_172_5；PDF 第 172 页 · b_172_6；PDF 第 172 页 · b_172_7；PDF 第 172 页 · b_172_10；PDF 第 173 页 · b_173_2；PDF 第 173 页 · b_173_3；PDF 第 173 页 · b_173_4；PDF 第 173 页 · b_173_5；PDF 第 173 页 · b_173_6；PDF 第 173 页 · b_173_7；PDF 第 173 页 · b_173_9；PDF 第 173 页 · b_173_11

有向完全图能否只检查边数等于 n(n-1)？¶

何时用：简单有向图判断任意不同顶点 u、v 间是否同时存在 u→v 与 v→u。

思路步骤：

在“简单、无自环、无重边”前提下，边数 n(n-1) 与有向完全等价。
若不能完全信任图元数据，应逐顶点扫描出边。
每个顶点应恰有 n-1 个不同的非自身出邻点。
十字链表中从 first_out 沿 tlink 扫描。

伪代码/关键模板：

int ac_is_complete_directed(const ACOLGraph *g) {
    if (g == NULL || g->n < 0 || g->n > AC_MAXV) return 0;
    for (int u = 0; u < g->n; ++u) {
        unsigned char seen[AC_MAXV] = {0};
        int count = 0;
        for (const ACArcBox *p = g->first_out[u]; p != NULL; p = p->tlink) {
            if (p->tail != u || p->head < 0 || p->head >= g->n
                || p->head == u || seen[p->head]) return 0;
            seen[p->head] = 1;
            ++count;
        }
        if (count != g->n - 1) return 0;
    }
    return 1;
}

复杂度：扫描全部出边 O(n+e)，临时标记 O(n)。

易错边界：只看 numEdges 的公式依赖简单图与元数据准确；十字链表出边必须沿 tlink；自环不能替代指向其他顶点的弧。

回源 · PDF 第 174 页 · b_174_0；PDF 第 174 页 · b_174_1；PDF 第 174 页 · b_174_2；PDF 第 174 页 · b_174_3；PDF 第 174 页 · b_174_4；PDF 第 174 页 · b_174_5；PDF 第 174 页 · b_174_6；PDF 第 174 页 · b_174_7；PDF 第 174 页 · b_174_10；PDF 第 174 页 · b_174_13；PDF 第 174 页 · b_174_18；PDF 第 174 页 · b_174_22；PDF 第 174 页 · b_174_23；PDF 第 174 页 · b_174_24；PDF 第 175 页 · b_175_0

统考真题路线¶

2021 EL 路径，为什么连通前提下只需数奇度顶点？¶

何时用：无向连通图、边集非空，判断是否存在经过每条边恰一次的欧拉通路/回路。

思路步骤：

对邻接矩阵每一行统计顶点度。
统计奇度顶点数 odd。
连通图存在欧拉回路当 odd=0；存在开放欧拉通路当 odd=2。
因而题目所称 EL 路径存在当且仅当 odd 为 0 或 2。

伪代码/关键模板：

int ac_has_el_path_connected(const ACMatrixGraph *g) {
    if (g == NULL || g->n <= 0 || g->n > AC_MAXV || g->m <= 0) return 0;
    int odd = 0;
    for (int u = 0; u < g->n; ++u) {
        int degree = 0;
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] != 0) ++degree;
        }
        if ((degree & 1) != 0) ++odd;
    }
    return odd == 0 || odd == 2;
}

复杂度：邻接矩阵时间 O(n²)，额外空间 O(1)。

易错边界：结论依赖题目已保证无向且连通；推广到一般图时，还必须检查所有非零度顶点属于同一连通分量。

回源 · PDF 第 175 页 · b_175_1；PDF 第 175 页 · b_175_2；PDF 第 175 页 · b_175_3；PDF 第 175 页 · b_175_4；PDF 第 175 页 · b_175_5；PDF 第 175 页 · b_175_6；PDF 第 175 页 · b_175_7；PDF 第 175 页 · b_175_8；PDF 第 175 页 · b_175_9；PDF 第 175 页 · b_175_10；PDF 第 175 页 · b_175_11；PDF 第 175 页 · b_175_12；PDF 第 176 页 · b_176_0；PDF 第 176 页 · b_176_2

2023 K 顶点，怎样在一次矩阵双循环中同时算入度和出度？¶

何时用：有向邻接矩阵，输出所有 outdegree>indegree 的顶点并返回数量。

思路步骤：

固定顶点 i。
扫描 j：edge[i][j] 非零则出度加一；edge[j][i] 非零则入度加一。
若出度大于入度，输出/回调 i 并计数。
换下一个 i 时重新清零两种度数。

伪代码/关键模板：

int ac_emit_k_vertices(const ACMatrixGraph *g, void (*emit)(int vertex)) {
    if (g == NULL || g->n <= 0 || g->n > AC_MAXV) return 0;
    int count = 0;
    for (int i = 0; i < g->n; ++i) {
        int indegree = 0, outdegree = 0;
        for (int j = 0; j < g->n; ++j) {
            if (g->edge[i][j] != 0) ++outdegree;
            if (g->edge[j][i] != 0) ++indegree;
        }
        if (outdegree > indegree) {
            if (emit != NULL) emit(i);
            ++count;
        }
    }
    return count;
}

复杂度：时间 O(n²)，额外空间 O(1)。

易错边界：行是出度、列是入度；两个 if 不能写成 else-if，因为 i→j 与 j→i 可同时存在；每轮必须清零。

回源 · PDF 第 176 页 · b_176_3；PDF 第 176 页 · b_176_4；PDF 第 176 页 · b_176_5；PDF 第 176 页 · b_176_6；PDF 第 176 页 · b_176_8；PDF 第 176 页 · b_176_9；PDF 第 176 页 · b_176_10；PDF 第 176 页 · b_176_11；PDF 第 176 页 · b_176_12；PDF 第 176 页 · b_176_13；PDF 第 176 页 · b_176_14；PDF 第 177 页 · b_177_0；PDF 第 177 页 · b_177_1；PDF 第 177 页 · b_177_2

2024 唯一拓扑序，为什么每一轮都必须恰有一个零入度点？¶

何时用：判断有向图是否存在且仅存在一个拓扑序列。

思路步骤：

统计入度，把所有零入度顶点入队。
每次选择前检查当前候选数 rear-front。
候选数为 0 表示环/无法继续；大于 1 表示至少有两种合法选择，序列不唯一。
候选恰为 1 时出队，删除其出边并加入新零入度点。
成功处理恰好 n 个顶点才返回 1。

伪代码/关键模板：

int ac_unique_topological_order(const ACMatrixGraph *g) {
    if (g == NULL || g->n < 0 || g->n > AC_MAXV) return 0;
    int indegree[AC_MAXV] = {0};
    int queue[AC_MAXV], front = 0, rear = 0, processed = 0;
    for (int u = 0; u < g->n; ++u) {
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] != 0) ++indegree[v];
        }
    }
    for (int v = 0; v < g->n; ++v) {
        if (indegree[v] == 0) queue[rear++] = v;
    }
    while (processed < g->n) {
        if (rear - front != 1) return 0;
        int u = queue[front++];
        ++processed;
        for (int v = 0; v < g->n; ++v) {
            if (g->edge[u][v] != 0 && --indegree[v] == 0) {
                queue[rear++] = v;
            }
        }
    }
    return 1;
}

复杂度：邻接矩阵 O(n²)，辅助空间 O(n)。

易错边界：初始或中途没有候选说明有环，不是“唯一”；多个候选立即证明不唯一；空图唯一序列的数学口径与考试非空图口径应按题目说明。

回源 · PDF 第 177 页 · b_177_3；PDF 第 177 页 · b_177_4；PDF 第 178 页 · b_178_0；PDF 第 178 页 · b_178_1；PDF 第 178 页 · b_178_2；PDF 第 178 页 · b_178_3；PDF 第 178 页 · b_178_4；PDF 第 178 页 · b_178_8；PDF 第 178 页 · b_178_10；PDF 第 178 页 · b_178_11；PDF 第 178 页 · b_178_13；PDF 第 179 页 · b_179_0；PDF 第 180 页 · b_180_0；PDF 第 180 页 · b_180_5；PDF 第 180 页 · b_180_8

第5章 图算法