tsort:UNIX/Linux执行拓扑排序

时间:2020-01-09 10:46:06  来源:igfitidea点击:

问题描述:如何在不使用C或者其他编程语言编写代码的情况下执行拓扑排序或者拓扑排序?
如何使用Shell脚本对给定的FILE执行拓扑排序?

A.有向无环图(DAG)的拓扑排序或者拓扑排序是其节点的线性排序,其中,每个节点位于其出站边缘的所有节点之前。
每个DAG具有一种或者多种拓扑类型。
考虑以下示例输入数据(input.txt):

a b c
     d
     e f
     b c d e

拓扑排序应产生如下输出:

a
     b
     c
     d
     e
     f

tsort命令

使用tsort命令进行拓扑排序:

$ tsort input.txt
$ tsort input.txt > output.txt

关于tsort的说明

之所以存在tsort,是因为Unix链接器的早期版本仅一次按顺序处理了一个存档文件。
当ld读取存档中的每个对象时,它会根据是否定义了链接中当时未定义的符号来决定程序中是否需要该对象。
该实用程序失去了重要性,对于任何严重/复杂的数据排序用途,您都应使用C或者其他编程语言。