Go语言实现拓扑排序（Topological Sorting）算法

Go语言实现拓扑排序（Topological Sorting）算法在

Go语言中实现拓扑排序也可以使用Kahn's算法，步骤和Python版本的实现类似。以下是一个完整的Go语言实现：

package main

import (
	"fmt"
)

// topologicalSort performs a topological sort on a directed graph.
// numCourses is the number of courses, and prerequisites is a list of prerequisite pairs.
func topologicalSort(numCourses int, prerequisites [][]int) []int {
	// Create an adjacency list and an in-degree array
	adjList := make(map[int][]int)
	inDegree := make([]int, numCourses)

	// Populate the adjacency list and in-degree array
	for _, prereq := range prerequisites {
		dest, src := prereq[0], prereq[1]
		adjList[src] = append(adjList[src], dest)
		inDegree[dest]++
	}

	// Initialize a queue with all nodes having in-degree of 0
	queue := []int{}
	for i := 0; i < numCourses; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	var topologicalOrder []int

	// Process until the queue becomes empty
	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]
		topologicalOrder = append(topologicalOrder, vertex)

		// For each neighbor, reduce its in-degree by 1
		for _, neighbor := range adjList[vertex] {
			inDegree[neighbor]--
			// If in-degree becomes 0, add it to the queue
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	// Check if topological sort is possible or not
	if len(topologicalOrder) == numCourses {
		return topologicalOrder
	} else {
		return []int{} // Return an empty list if there is a cycle in the graph
	}
}

func main() {
	numCourses := 6
	prerequisites := [][]int{
		{5, 2},
		{5, 0},
		{4, 0},
		{4, 1},
		{2, 3},
		{3, 1},
	}

	result := topologicalSort(numCourses, prerequisites)
	fmt.Println(result)
}

这个Go语言实现的步骤如下：

1. 创建邻接表（adjList）和入度数组（inDegree）。
2. 遍历所有边，填充邻接表和入度数组。
3. 将所有入度为0的节点加入队列。
4. 依次处理队列中的节点，更新其邻接节点的入度，并将新的入度为0的节点加入队列。
5. 最终，如果排序结果中的节点数量等于图中的节点数，则返回拓扑排序结果；否则，说明图中有环，返回空列表。

这个实现假设输入是一个表示课程和先修课程的有向无环图（DAG），并返回一个可能的课程安排顺序。如果图中存在环，则返回空列表。