Function kahnSort

packages/runtime-core/src/utils/DependencyUtils.ts:185–243

* @zh 使用 Kahn 算法进行拓扑排序 * @en Topological sort using Kahn's algorithm * * @zh Kahn 算法优势： * - 能够检测循环依赖 * - 返回所有循环中的节点 * - 时间复杂度 O(V + E)

(
    items: T[],
    resolveId: (id: string) => string
)

 * - 时间复杂度 O(V + E)
 */
function kahnSort<T extends IDependable>(
    items: T[],
    resolveId: (id: string) => string
): TopologicalSortResult<T> {
    const itemMap = new Map<string, T>();
    const graph = new Map<string, Set<string>>();
    const inDegree = new Map<string, number>();

    // 构建节点映射
    for (const item of items) {
        itemMap.set(item.id, item);
        graph.set(item.id, new Set());
        inDegree.set(item.id, 0);
    }

    // 构建边（依赖 -> 被依赖者）
    for (const item of items) {
        for (const dep of item.dependencies || []) {
            const depId = resolveId(dep);
            if (itemMap.has(depId)) {
                graph.get(depId)!.add(item.id);
                inDegree.set(item.id, (inDegree.get(item.id) || 0) + 1);
            }
        }
    }

    // 收集入度为 0 的节点
    const queue: string[] = [];
    for (const [id, degree] of inDegree) {
        if (degree === 0) {
            queue.push(id);
        }
    }

    // BFS 处理
    const sorted: T[] = [];
    while (queue.length > 0) {
        const current = queue.shift()!;
        sorted.push(itemMap.get(current)!);

        for (const neighbor of graph.get(current) || []) {
            const newDegree = (inDegree.get(neighbor) || 0) - 1;
            inDegree.set(neighbor, newDegree);
            if (newDegree === 0) {
                queue.push(neighbor);
            }
        }
    }

    // 检查循环依赖
    if (sorted.length !== items.length) {
        const cycleIds = items
            .filter(item => !sorted.includes(item))
            .map(item => item.id);
        return { sorted, hasCycles: true, cycleIds };
    }

    return { sorted, hasCycles: false };