DAG与有向无环图拓扑排序

📖 算法原理：入度计数与 Kahn 队列排除法

拓扑排序（Topological Sort）是对有向无环图（DAG）的顶点的一种线性排序，使得若存在一条有向边 $u \to v$，则在序列中 $u$ 必排在 $v$ 之前。

📐 Kahn 拓扑排序算法流程

统计入度（In-degree）：统计图中每个顶点的入度（即以该点为终点的有向边数）。
队列初始化：将所有初始入度为 0 的顶点推入辅助队列 queue 中。
迭代出队消除：循环执行直到队列为空：

从队列首部弹出一个顶点 $u$，将其加入拓扑排序结果序列。
遍历以 $u$ 为起点的所有出边 $u \to v$。断开并消除这些出边，使得终点 $v$ 的入度自减 1（即 in_degree[v]--）。
若入度减至 0，说明 $v$ 的所有前置依赖已消解，将其推入队列。

环路检测判定：如果输出结果序列中的顶点数小于图的顶点总数 $N$，说明图中存在循环依赖（即环路）！

📥 入度为0的排队队列 (Kahn Queue)

队列为空

选择图形：

演示速度：

选择图Preset并点击"开始拓扑排序"观摩 Kahn 排队排除全过程。

🏁 输出拓扑线性序列 (Topological Order List)：

排队中

🕸️ 有向流光连线拓扑图与入度状态 (Directed Topology & In-Degree Counters)

vector<int> topo;  // 记录拓扑排序输出序列
int indegree[MAXN]; // 记录每个顶点的入度

bool kahn() {
    queue<int> q;
    // 将所有初始入度为 0 的节点推入队列
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u); // 出队并记入拓扑序列
        
        for (int v : g[u]) {
            indegree[v]--; // 割裂连线，消除入度计数
            if (indegree[v] == 0) {
                q.push(v); // 依赖全部清除的节点进入队列
            }
        }
    }
    // 若拓扑输出点数不足 n，说明图中有环！
    return topo.size() == n; 
}

📋 算法执行步骤历史