题目
有向图(具有单向边的图)的拓扑排序是其顶点的线性排序，这样对于从顶点U到顶点V的每一条有向边(U, V)，在排序中U排在V之前。给出一个有向图，求其顶点的拓扑顺序。
示例1：
输入：Vertices=4, Edges=[3,2], [3,0], [2,0], [2,1]
输出：3,2,0,1 和 3,2,1,0
解答
Java
import java.util.*;
class TopologicalSort {
public static List<Integer> sort(int vertices, int[][] edges) {
List<Integer> sortedOrder = new ArrayList<>();
if (vertices <= 0)
return sortedOrder;
// a. 初始化图
HashMap<Integer, Integer> inDegree = new HashMap<>(); // 计算每个节点的入度
HashMap<Integer, List<Integer>> graph = new HashMap<>(); // 邻接链表图
for (int i = 0; i < vertices; i++) {
inDegree.put(i, 0);
graph.put(i, new ArrayList<Integer>());
}
// b. 构建图
for (int i = 0; i < edges.length; i++) {
int parent = edges[i][0], child = edges[i][1];
graph.get(parent).add(child); // 将孩子添加到父结点的list中
inDegree.put(child, inDegree.get(child) + 1); // 增加孩子的入度
}
// c. 找到所有的源节点，源节点入度为0
Queue<Integer> sources = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0)
sources.add(entry.getKey());
}
// d. 对于每一个源节点，添加它到已排序list中，同时将它的所有孩子节点入度减一
// 如果一个孩子节点的入度变成1，添加它到源队列中
while (!sources.isEmpty()) {
int vertex = sources.poll();
sortedOrder.add(vertex);
List<Integer> children = graph.get(vertex); // 获取该节点的子节点，并将入度减1
for (int child : children) {
inDegree.put(child, inDegree.get(child) - 1);
if (inDegree.get(child) == 0)
sources.add(child);
}
}
if (sortedOrder.size() != vertices) // 排序了的list的大小和图的节点数不一致，则图中存在环
return new ArrayList<>();
return sortedOrder;
}
public static void main(String[] args) {
List<Integer> result = TopologicalSort.sort(4,
new int[][] { new int[] { 3, 2 }, new int[] { 3, 0 }, new int[] { 2, 0 }, new int[] { 2, 1 } });
System.out.println(result);
result = TopologicalSort.sort(5, new int[][] { new int[] { 4, 2 }, new int[] { 4, 3 }, new int[] { 2, 0 },
new int[] { 2, 1 }, new int[] { 3, 1 } });
System.out.println(result);
result = TopologicalSort.sort(7, new int[][] { new int[] { 6, 4 }, new int[] { 6, 2 }, new int[] { 5, 3 },
new int[] { 5, 4 }, new int[] { 3, 0 }, new int[] { 3, 1 }, new int[] { 3, 2 }, new int[] { 4, 1 } });
System.out.println(result);
}
}JavaScript
function topologicalSort(vertices, edges) {
let sortedOrder = [];
if (vertices <= 0) return sortedOrder;
// a. 初始化图
let inDegree = new Map(); // 计算每个节点的入度
let graph = new Map(); // 邻接链表图
for (let i = 0; i < vertices; i++) {
inDegree.set(i, 0);
graph.set(i, []);
}
// b. 构建图
for (let i = 0; i < edges.length; i++) {
let [parent, child] = edges[i];
graph.get(parent).push(child); // 将孩子添加到父结点的数组中
inDegree.set(child, inDegree.get(child) + 1); // 增加孩子的入度
}
// c. 找到所有的源节点，源节点入度为0
let sources = [];
for (let [key, value] of inDegree) {
if (value === 0) sources.push(key);
}
// d. 对于每一个源节点，添加它到已排序数组中，同时将它的所有孩子节点入度减一
// 如果一个孩子节点的入度变成1，添加它到源数组中
while (sources.length > 0) {
let vertex = sources.shift();
sortedOrder.push(vertex);
let children = graph.get(vertex); // 获取该节点的子节点，并将入度减1
for (let child of children) {
inDegree.set(child, inDegree.get(child) - 1);
if (inDegree.get(child) === 0) sources.push(child);
}
}
if (sortedOrder.length !== vertices) return [];
return sortedOrder;
}
let result = topologicalSort(4, [
[3, 2],
[3, 0],
[2, 0],
[2, 1]
]);
console.log(result);
result = topologicalSort(5, [
[4, 2],
[4, 3],
[2, 0],
[2, 1],
[3, 1]
]);
console.log(result);
result = topologicalSort(7, [
[6, 4],
[6, 2],
[5, 3],
[5, 4],
[3, 0],
[3, 1],
[3, 2],
[4, 1]
]);
console.log(result);Python
from collections import defaultdict, deque
def topological_sort(vertices, edges):
sorted_order = []
if vertices <= 0:
return sorted_order
# a. 初始化图
in_degree = defaultdict(int) # 计算每个节点的入度
graph = defaultdict(list) # 邻接链表图
for i in range(vertices):
in_degree[i] = 0
graph[i] = []
# b. 构建图
for edge in edges:
parent, child = edge
graph[parent].append(child) # 将孩子添加到父结点的列表中
in_degree[child] += 1 # 增加孩子的入度
# c. 找到所有的源节点，源节点入度为0
sources = deque()
for key, value in in_degree.items():
if value == 0:
sources.append(key)
# d. 对于每一个源节点，添加它到已排序列表中，同时将它的所有孩子节点入度减一
# 如果一个孩子节点的入度变成0，添加它到源队列中
while sources:
vertex = sources.popleft()
sorted_order.append(vertex)
children = graph[vertex] # 获取该节点的子节点，并将入度减1
for child in children:
in_degree[child] -= 1
if in_degree[child] == 0:
sources.append(child)
if len(sorted_order) != vertices: # 排序了的列表的大小和图的节点数不一致，则图中存在环
return []
return sorted_order
result = topological_sort(4, [
[3, 2],
[3, 0],
[2, 0],
[2, 1]
])
print(result)
result = topological_sort(5, [
[4, 2],
[4, 3],
[2, 0],
[2, 1],
[3, 1]
])
print(result)
result = topological_sort(7, [
[6, 4],
[6, 2],
[5, 3],
[5, 4],
[3, 0],
[3, 1],
[3, 2],
[4, 1]
])
print(result)Go
package main
import (
"fmt"
)
type Queue []int
func (q *Queue) Push(item int) {
*q = append(*q, item)
}
func (q *Queue) Pop() int {
item := (*q)[0]
*q = (*q)[1:]
return item
}
func topologicalSort(vertices int, edges [][]int) []int {
sortedOrder := []int{}
if vertices <= 0 {
return sortedOrder
}
// a. 初始化图
inDegree := make(map[int]int) // 计算每个节点的入度
graph := make(map[int][]int) // 邻接链表图
for i := 0; i < vertices; i++ {
inDegree[i] = 0
graph[i] = []int{}
}
// b. 构建图
for i := 0; i < len(edges); i++ {
parent, child := edges[i][0], edges[i][1]
graph[parent] = append(graph[parent], child) // 将孩子添加到父结点的切片中
inDegree[child]++ // 增加孩子的入度
}
// c. 找到所有的源节点，源节点入度为0
sources := Queue{}
for key, value := range inDegree {
if value == 0 {
sources.Push(key)
}
}
// d. 对于每一个源节点，添加它到已排序切片中，同时将它的所有孩子节点入度减一
// 如果一个孩子节点的入度变成0，添加它到源队列中
for len(sources) > 0 {
vertex := sources.Pop()
sortedOrder = append(sortedOrder, vertex)
children := graph[vertex] // 获取该节点的子节点，并将入度减1
for _, child := range children {
inDegree[child]--
if inDegree[child] == 0 {
sources.Push(child)
}
}
}
if len(sortedOrder) != vertices { // 排序了的切片的大小和图的节点数不一致，则图中存在环
return []int{}
}
return sortedOrder
}
func main() {
result := topologicalSort(4, [][]int{
{3, 2},
{3, 0},
{2, 0},
{2, 1},
})
fmt.Println(result)
result = topologicalSort(5, [][]int{
{4, 2},
{4, 3},
{2, 0},
{2, 1},
{3, 1},
})
fmt.Println(result)
result = topologicalSort(7, [][]int{
{6, 4},
{6, 2},
{5, 3},
{5, 4},
{3, 0},
{3, 1},
{3, 2},
{4, 1},
})
fmt.Println(result)
}