拓扑排序只有一个终点吗

拓扑排序并不要求只有一个终点，可以有多个终点。在有向无环图（DAG）中，拓扑排序是一种对图中节点进行线性排序的算法，使得所有的有向边从排在前面的节点指向排在后面的节点。如果一个有向图存在拓扑排序，那么这个图就是一个有向无环图。

在拓扑排序中，可以存在多个没有任何出边的节点，这些节点被称为终点或者叶子节点。它们可以在任意位置出现在排序结果中，因为它们没有任何依赖关系。所以，并不要求拓扑排序只有一个终点。

相关问题

写一个拓扑排序的代码

拓扑排序是一种经典的图论算法，用于解决有向无环图（DAG）的排序问题，其核心思想是通过不断删除入度为0的节点来确定图中节点的线性序列。以下是一个实现拓扑排序的 Python 代码：

from collections import deque

def topological_sort(graph):
    # 计算每个节点的入度
    in_degree = dict((u, 0) for u in graph)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    # 将入度为0的节点加入队列
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    
    # 不断删除入度为0的节点
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 判断是否存在环
    if len(result) != len(graph):
        raise ValueError("图中存在环")
    
    return result

该算法接受一个字典类型的图作为输入，其中键为节点，值为该节点指向的节点列表。例如，如果存在以下图：

A -> B -> C
|    ^
v    |
D -> E

则可以用以下代码表示：

graph = {
    'A': ['B', 'D'],
    'B': ['C', 'E'],
    'D': ['E'],
    'E': ['B'],
    'C': []
}

调用 `topological_sort(graph)` 将返回 `['A', 'D', 'E', 'B', 'C']`，表示该图的一种拓扑排序结果。

用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 实现拓扑排序的代码。