拓扑排序中用了哪些结构

拓扑排序是一种有序的图论算法，用于将有向无环图（DAG）中的节点按照顺序排列。它在许多领域都有着广泛的应用，如编译器优化、任务调度、依赖管理等。在拓扑排序中，我们使用了许多结构来实现算法，下面从多个角度来分析拓扑排序中用了哪些结构。

1. 邻接表

邻接表是图论中最基本的数据结构之一，它用于表示有向图/无向图的连接关系。在拓扑排序中，我们可以使用邻接表来表示图中的节点及其连接关系。具体来说，邻接表是由一个数组和每个节点的连边数组组成的。这个数组中有顺序地存储了每个节点和它的所有连边。

2. 入度表

入度是指有向图中指向该节点的边的数量。在拓扑排序中，我们需要根据每个节点的入度来进行排序。因此，我们可以创建一个入度表来记录每个节点的入度数量。当图中的某个节点被遍历到时，我们需要遍历它所连接的所有节点，并将所有节点的入度减 1。当一个节点的入度为 0 时，它就可以被加入到拓扑排序的结果中。

3. 队列

队列是一种先进先出的数据结构，非常适合用于存储需要在特定顺序下处理的数据。在拓扑排序中，我们需要使用队列来存储入度为 0 的节点。当所有的入度为 0 的节点被加入到队列中之后，我们可以按照队列中的顺序依次将节点加入到拓扑排序的结果中。

4. 拓扑排序结果集

拓扑排序结果集是一个额外的数据结构，用于记录我们最后的排序结果。在遍历完所有的节点之后，我们需要遍历拓扑排序结果集并将其中的所有节点按照顺序输出。

5. 临时变量

在实现拓扑排序时，我们需要使用一些临时变量来帮助记录当前节点的入度以及其他一些需要的信息。通常这些变量的存储方式和大小都是固定的，可以在代码中进行预定义。

综上所述，拓扑排序中用了邻接表来表示图中节点连边的关系、用入度表记录每个节点的入度、使用队列记录入度为 0 的节点、用拓扑排序结果集来存储最终排序结果、以及使用临时变量来辅助实现算法。