如何在T-SQL的拓扑排序实现中处理循环问题？

Khan算法本身具备循环检测的能力——环内节点的入度永远无法降到0，你的无限循环问题本质是没在迭代中加入循环终止判断。下面是修正后的实现，同时附带环的识别逻辑：

修正后的迭代式Khan算法脚本 #

假设你的依赖关系存储在Edges(FromNode int, ToNode int)，所有节点存储在Nodes(Node int)：

DECLARE @InDegree TABLE (Node int, Degree int);
DECLARE @TopoOrder TABLE (Node int, OrderRank int);
DECLARE @ProcessedTotal int = 0;
DECLARE @TotalNodes int;

-- 获取总节点数，用于后续判断是否存在环
SELECT @TotalNodes = COUNT(*) FROM Nodes;

-- 初始化每个节点的入度
INSERT INTO @InDegree (Node, Degree)
SELECT n.Node, ISNULL(COUNT(e.FromNode), 0)
FROM Nodes n
LEFT JOIN Edges e ON n.Node = e.ToNode
GROUP BY n.Node;

WHILE 1=1
BEGIN
    DECLARE @BatchCount int = 0;

    -- 取出当前所有入度为0的节点，加入排序结果
    INSERT INTO @TopoOrder (Node, OrderRank)
    SELECT Node, @ProcessedTotal + ROW_NUMBER() OVER (ORDER BY Node)
    FROM @InDegree
    WHERE Degree = 0;

    SET @BatchCount = @@ROWCOUNT;
    SET @ProcessedTotal += @BatchCount;

    -- 核心：如果本次循环没有处理任何节点，说明存在环，直接终止
    IF @BatchCount = 0
        BREAK;

    -- 移除已处理的节点（入度为0的节点）
    DELETE FROM @InDegree WHERE Degree = 0;

    -- 更新剩余节点的入度：减去已处理节点的出边
    UPDATE id
    SET Degree = id.Degree - 1
    FROM @InDegree id
    JOIN Edges e ON id.Node = e.ToNode
    WHERE e.FromNode IN (
        SELECT Node FROM @TopoOrder 
        WHERE OrderRank > @ProcessedTotal - @BatchCount
    );
END

-- 检查是否存在未处理节点（即环）
IF @ProcessedTotal < @TotalNodes
BEGIN
    -- 抛出错误并列出环内节点
    DECLARE @CycleNodes NVARCHAR(MAX);
    SELECT @CycleNodes = STRING_AGG(Node, ', ') FROM @InDegree;
    RAISERROR('检测到循环，涉及节点：%s', 16, 1, @CycleNodes);
END
ELSE
BEGIN
    -- 输出拓扑排序结果
    SELECT * FROM @TopoOrder ORDER BY OrderRank;
END

关键修复点 #

1. 循环终止判断：每次循环统计@BatchCount（本次处理的节点数），当它为0时，说明没有节点的入度能降到0，必然存在环，直接跳出循环，避免无限挂起。
2. 环的识别：通过对比已处理节点数@ProcessedTotal和总节点数@TotalNodes，判断是否存在环；未处理的节点就是环的组成部分。
3. 入度更新逻辑：精准定位刚处理的节点，只更新受其影响的节点入度，避免不必要的计算。

可选：精准找出环的路径 #

如果需要明确环的具体路径，可在检测到环后，从某个未处理节点出发递归查找闭环：

IF @ProcessedTotal < @TotalNodes
BEGIN
    DECLARE @StartNode int = (SELECT TOP 1 Node FROM @InDegree);
    WITH CycleCTE AS (
        SELECT Node, CAST(Node AS NVARCHAR(MAX)) AS Path
        FROM @InDegree WHERE Node = @StartNode
        UNION ALL
        SELECT e.ToNode, c.Path + ' -> ' + CAST(e.ToNode AS NVARCHAR(MAX))
        FROM CycleCTE c
        JOIN Edges e ON c.Node = e.FromNode
        JOIN @InDegree id ON e.ToNode = id.Node
        WHERE CHARINDEX(CAST(e.ToNode AS NVARCHAR(MAX)), c.Path) = 0
    )
    SELECT '循环路径：' + Path AS CycleInfo
    FROM CycleCTE
    WHERE Node = @StartNode AND LEN(Path) > LEN(CAST(@StartNode AS NVARCHAR(MAX)));
END

内容的提问来源于stack exchange，提问作者dlp_dev