当前位置： 面试刷题>> 拓扑排序 (经典算法题500道)
### 题目描述补充
**题目：拓扑排序**
给定一个有向无环图（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 示例
```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 示例
```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 示例
```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));
```
**码小课网站中有更多相关内容分享给大家学习**，包括图论的其他算法、数据结构的应用等，欢迎访问学习。