用golang写一个拓扑排序

可以使用 golang 中的 sort 包和 container 包来实现拓扑排序。具体实现步骤如下：

1. 定义一个结构体来表示有向图中的节点，包含节点的值和指向该节点的边的集合。

type Node struct {
Val int
Edges []*Node
}

2. 定义一个函数来进行拓扑排序，该函数接受一个有向图的节点集合作为参数，并返回排序后的节点集合。

func TopologicalSort(nodes []*Node) []*Node {
// 统计每个节点的入度
inDegrees := make(map[*Node]int)
for _, node := range nodes {
for _, edge := range node.Edges {
inDegrees[edge]++
}
}

// 将入度为 0 的节点加入队列
queue := make([]*Node, 0)
for _, node := range nodes {
if inDegrees[node] == 0 {
queue = append(queue, node)
}
}

// 依次取出队列中的节点，并将其指向的节点的入度减 1
sortedNodes := make([]*Node, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
sortedNodes = append(sortedNodes, node)
for _, edge := range node.Edges {
inDegrees[edge]--
if inDegrees[edge] == 0 {
queue = append(queue, edge)
}
}
}

return sortedNodes
}

3. 创建节点并建立边的关系，然后调用 TopologicalSort 函数进行拓扑排序。

func main() {
// 创建节点
node1 := &Node{Val: 1}
node2 := &Node{Val: 2}
node3 := &Node{Val: 3}
node4 := &Node{Val: 4}
node5 := &Node{Val: 5}

// 建立边的关系
node1.Edges = []*Node{node2, node3}
node2.Edges = []*Node{node4}
node3.Edges = []*Node{node4, node5}

// 进行拓扑排序
sortedNodes := TopologicalSort([]*Node{node1, node2, node3, node4, node5})

// 输出排序结果
for _, node := range sortedNodes {
fmt.Printf("%d ", node.Val)
}
// 输出结果为：1 3 2 5 4
}

以上就是用 golang 实现拓扑排序的代码。