拓扑排序

📌 核心概念

拓扑排序：将有向无环图（DAG）的所有顶点排成一个线性序列，使得所有有向边从前指向后。

应用场景：

• 任务调度（前置依赖）
• 课程安排
• 编译顺序

💻 算法实现

🎯 经典应用

Go 代码

func topologicalSort(n int, edges [][]int) []int {
    graph := make(map[int][]int)
    inDegree := make([]int, n)
 
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        inDegree[v]++
    }
 
    queue := []int{}
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
 
    result := []int{}
 
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
 
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
 
    if len(result) != n {
        return []int{}
    }
    return result
}

🎯 经典题目

题目	LeetCode	关键点
课程表	207	检测环
课程表II	210	拓扑排序
课程表IV	1462	可达性

---

返回：图算法