如何在拓扑排序结果中识别独立的节点链？

原本通过拓扑排序处理节点结构时，仅能得到全局的拓扑顺序，无法区分图中的独立节点链（例如示例中的J-L链与B-C-D/E-H-I链属于两个独立的连通分量）。需要修改现有拓扑排序函数，实现识别并分组这些独立链的功能。

给定节点数据结构 #

[
    {name: 'B', input: []},
    {name: 'C', input: ['B']},
    {name: 'D', input: ['C']},
    {name: 'E', input: ['C']},
    {name: 'H', input: ['E']},
    {name: 'I', input: ['D', 'H']},
    {name: 'J', input: []},
    {name: 'L', input: ['J']},
]

当前使用的拓扑排序代码 #

orderModelNodesTopologically(nodes: ExternalInputGraphNode[]): string[] {
    const adjacencyList = this.createAdjacencyList(nodes);
    const vertices = Object.keys(adjacencyList);
    const visited = {};
    const topNums = {};
    let n = vertices.length - 1;
    for (const v of vertices) {
        if (!visited[v]) {
            n = this.depthFirstSearch(v, n, visited, topNums, adjacencyList);
        }
    }
    return Object.keys(topNums).sort((a, b) => topNums[a] - topNums[b]);
}

createAdjacencyList(nodes: ExternalInputGraphNode[]) {
    const list = {};
    nodes.forEach(node => list[node.name] = []);
    nodes.forEach(node => {
        node.input.forEach(inp => {
            if (list[inp] !== undefined) {
                list[inp].push(node.name);
            }
        });
    });
    return list;
}

depthFirstSearch(nodeName: string, n: number, visited: {[key: string]: boolean}, topNums: {[key: string]: number}, adjacencyList: {[key: string]: string[]}) {
    visited[nodeName] = true;
    const neighbors = adjacencyList[nodeName];
    for (const neighbor of neighbors) {
        if (!visited[neighbor]) {
            n = this.depthFirstSearch(neighbor, n, visited, topNums, adjacencyList);
        }
    }
    topNums[nodeName] = n;
    return n - 1;
}

修改方案 #

核心思路是在拓扑排序过程中，追踪每个连通分量（即独立节点链所在的子图），将每个分量内的节点单独进行拓扑排序并分组存储。

修改后的完整代码 #

// 修改返回类型为二维数组，每组对应一条独立链的拓扑顺序
orderModelNodesTopologically(nodes: ExternalInputGraphNode[]): string[][] {
    const adjacencyList = this.createAdjacencyList(nodes);
    const vertices = Object.keys(adjacencyList);
    const visited = {};
    const components: string[][] = [];

    for (const v of vertices) {
        if (!visited[v]) {
            const componentNodes: string[] = [];
            const topNums = {};
            let n = vertices.length - 1;
            // 对当前连通分量执行DFS，收集节点并计算拓扑序号
            n = this.depthFirstSearch(v, n, visited, topNums, adjacencyList, componentNodes);
            // 对当前分量的节点按拓扑序号排序，得到该分量的拓扑顺序
            const sortedComponent = componentNodes.sort((a, b) => topNums[a] - topNums[b]);
            components.push(sortedComponent);
        }
    }
    return components;
}

createAdjacencyList(nodes: ExternalInputGraphNode[]) {
    const list = {};
    nodes.forEach(node => list[node.name] = []);
    nodes.forEach(node => {
        node.input.forEach(inp => {
            if (list[inp] !== undefined) {
                list[inp].push(node.name);
            }
        });
    });
    return list;
}

// 新增componentNodes参数，用来收集当前连通分量的所有节点
depthFirstSearch(nodeName: string, n: number, visited: {[key: string]: boolean}, topNums: {[key: string]: number}, adjacencyList: {[key: string]: string[]}, componentNodes: string[]) {
    visited[nodeName] = true;
    componentNodes.push(nodeName); // 将当前节点加入所在分量的列表
    const neighbors = adjacencyList[nodeName];
    for (const neighbor of neighbors) {
        if (!visited[neighbor]) {
            n = this.depthFirstSearch(neighbor, n, visited, topNums, adjacencyList, componentNodes);
        }
    }
    topNums[nodeName] = n;
    return n - 1;
}

修改说明 #

1. 返回类型调整：将主函数的返回值从string[]改为string[][]，每个子数组对应一个独立节点链的拓扑排序结果
2. 连通分量追踪：遍历未访问节点时，为每个新的连通分量创建单独的componentNodes列表和topNums映射，确保分量间的拓扑计算独立
3. DFS增强：在DFS函数中新增componentNodes参数，用于收集当前连通分量的所有节点
4. 分量内排序：对每个连通分量的节点，根据拓扑序号排序后存入结果数组

运行结果 #

针对示例输入，修改后的函数会返回类似如下的结果（拓扑排序存在多种合法顺序，以下为其中一种）：

[
    ['B', 'C', 'D', 'E', 'H', 'I'],
    ['J', 'L']
]

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