题目描述补充

题目：拓扑排序

给定一个有向无环图（DAG, Directed Acyclic Graph），请实现一个算法来对该图进行拓扑排序。拓扑排序是对图中的所有顶点进行排序，使得对于任何从顶点u到顶点v的有向边(u, v)，u在排序中都出现在v之前。拓扑排序的结果可能不是唯一的。

示例

假设有以下有向无环图：

1 -> 2
1 -> 3
2 -> 3

一个可能的拓扑排序是 [1, 2, 3]，但 [1, 3, 2] 也是有效的，因为所有从u到v的边都满足u在v之前。

解题思路

1. 入度表：首先，计算图中每个顶点的入度（即指向该顶点的边的数量）。
2. 队列：使用队列来存储入度为0的顶点，这些顶点可以作为拓扑排序的起始点。
3. 遍历：从队列中取出一个顶点，将其添加到拓扑排序的结果中，并遍历该顶点的所有邻接点，将它们的入度减1。如果某个邻接点的入度变为0，则将其加入队列。
4. 检查：如果最终拓扑排序的结果中顶点的数量与图中顶点的总数不一致，则说明图中存在环，无法进行拓扑排序。

示例代码

PHP 示例

function topologicalSort($graph) {
    $inDegree = array_fill_keys(array_keys($graph), 0);
    $adjList = [];
    foreach ($graph as $node => $neighbors) {
        foreach ($neighbors as $neighbor) {
            $inDegree[$neighbor]++;
            $adjList[$node][] = $neighbor;
        }
    }

    $queue = new SplQueue();
    foreach ($inDegree as $node => $deg) {
        if ($deg === 0) {
            $queue->enqueue($node);
        }
    }

    $result = [];
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $result[] = $node;
        foreach ($adjList[$node] as $neighbor) {
            $inDegree[$neighbor]--;
            if ($inDegree[$neighbor] === 0) {
                $queue->enqueue($neighbor);
            }
        }
    }

    return count($result) === count($graph) ? $result : false; // 存在环则返回false
}

// 示例用法
$graph = [
    1 => [2, 3],
    2 => [3],
];
print_r(topologicalSort($graph));

Python 示例

from collections import deque, defaultdict

def topological_sort(graph):
    in_degree = defaultdict(int)
    adj_list = defaultdict(list)
    for node, neighbors in graph.items():
        for neighbor in neighbors:
            in_degree[neighbor] += 1
            adj_list[node].append(neighbor)

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in adj_list[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else False

# 示例用法
graph = {
    1: [2, 3],
    2: [3],
}
print(topological_sort(graph))

JavaScript 示例

function topologicalSort(graph) {
    const inDegree = {};
    const adjList = {};
    for (const node in graph) {
        inDegree[node] = 0;
        adjList[node] = [];
        for (const neighbor of graph[node]) {
            inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
            adjList[node].push(neighbor);
        }
    }

    const queue = [];
    for (const node in inDegree) {
        if (inDegree[node] === 0) {
            queue.push(node);
        }
    }

    const result = [];
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        for (const neighbor of adjList[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    return result.length === Object.keys(graph).length ? result : false;
}

// 示例用法
const graph = {
    1: [2, 3],
    2: [3],
};
console.log(topologicalSort(graph));

码小课网站中有更多相关内容分享给大家学习，包括图论的其他算法、数据结构的应用等，欢迎访问学习。