C语言实现拓扑排序及其输出序列

本文档提供了一段C语言源代码，用于实现拓扑排序算法，该算法通过回溯和深度优先搜索（Depth-First Search, DFS）来找到并输出所有可能的拓扑排序序列。拓扑排序是图论中的一个重要概念，主要用于有向无环图（Directed Acyclic Graph, DAG）中，它将顶点按照依赖关系排序，使得对于每条有向边(u, v)，节点u总在节点v之前。 首先，代码定义了几个全局变量：节点数n、边的数量m、指向边数组k的指针k1，以及记录节点入度的数组de。程序通过用户输入获取节点和边的信息，并动态分配内存。在主函数main中，首先初始化这些变量，然后读取边的信息，将边表示为邻接矩阵k，并更新对应节点的入度。 接下来，`taop`函数是核心部分，采用递归的方式进行拓扑排序。函数接收五个参数：一个地址数组adress用于存储排序后的序列，一个计数器num记录当前序列的位置，入度数组de，邻接矩阵k以及总的节点数n。 在`taop`函数中，遍历所有节点。当发现一个入度为0的节点i时，说明这个节点可以作为当前序列的一部分。将i添加到address数组中，递增num，然后递归地调用自身。在递归过程中，如果当前序列完成（num等于n），则打印出排序后的序列。递归返回后，将节点i的入度恢复为0，以准备处理下一个节点。 此过程会一直进行，直到所有可达节点都被处理过。值得注意的是，由于使用了回溯，这种方法可能会生成重复的序列，因为每次从入度为0的节点出发，都可以产生多个不同的排序路径。要消除重复，可以在递归结束后或递归过程中加入额外的逻辑来检查和避免生成相同的序列。 总结来说，这段C代码实现了拓扑排序算法，通过深度优先搜索和递归策略找出并输出DAG的所有可能排序序列。它适合初学者学习和理解拓扑排序的基本概念和编程实现。