图论搜索的拓扑本质：从分层 BFS 到依赖排序

图的本质：状态与依赖关系网

在算法的世界里，“万物皆可为图”：

• 网格迷宫的走法：坐标为顶点，上下左右移动为边。
• 任务编排与编译器依赖：软件包或目标文件为顶点，先修依赖为有向边。
• 状态机转移：业务状态为顶点，事件触发为有向边。

当图具备“有向”且“无环”的属性时，它被称为 DAG（Directed Acyclic Graph，有向无环图）。DAG 是所有因果链条与任务调度的数学抽象。

广度优先搜索（BFS）的自然分层性

为什么在**所有边权均为非负常数（例如全为 1）**的图上，BFS 求出的路径必然是最短路径？

因为 BFS 天然具备“水波扩散”的分层属性：

• 第 0 层：起点 $S$（距离 0）
• 第 1 层：与起点直接相连的所有未访问点（距离 1）
• 第 $k$ 层：从第 $k-1$ 层的点一步可达的新顶点（距离 $k$）

队列的先进先出（FIFO）特性保证了按距离单调不减的顺序逐层扩展。当首次触达终点 $T$ 时，当前层数即为全局最短距离。

拓扑排序（Kahn 算法）

拓扑排序的目标是将 DAG 的所有顶点排成一个线性序列，使得对于图中的任意有向边 $(u,v)$，$u$ 在序列中均出现在 $v$ 之前。

基于入度削减的 Kahn 算法 是最清晰且直观的工程解法：

// n 个顶点，编号 0 ~ n-1
std::vector<int> in_degree(n, 0);
for (const auto& [u, v] : edges) {
    in_degree[v]++;
}

std::queue<int> q;
for (int i = 0; i < n; ++i) {
    if (in_degree[i] == 0) {
        q.push(i); // 将所有无前置依赖的任务入队
    }
}

std::vector<int> topo_order;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    topo_order.push_back(u);

    for (int v : adj[u]) {
        if (--in_degree[v] == 0) {
            q.push(v); // 前置依赖全部消除，任务就绪
        }
    }
}

// 环检测判断：若拓扑序列长度 < 总顶点数，则图中有环（循环依赖）
bool has_cycle = (topo_order.size() < n);

环路诊断与 DFS 三色标记法

除了 Kahn 算法，DFS 三色标记法也是检测有向图环路的利器：

• 白色（0）：尚未访问。
• 灰色（1）：正在当前递归调用栈中（祖先节点）。若访问到灰色节点，立刻确认发现后向边（Back-edge），存在环路！
• 黑色（2）：该节点及其全部子孙节点均已访问完毕。

拓扑排序不仅是算法题目的常客，更是现代构建工具（Webpack, Bazel）、工作流调度引擎（Airflow）和微服务依赖启动的核心算法。