在许多应用中，有向无回路图可用于抽象具有发生先后顺序的事件，图的搜索算法可以用于解决具有先决条件的问题。假设我们要安排一系列任务，但是只有在某个任务的先决条件具备时才能着手完成这个任务。我们希望以某种先后顺序组织这些任务，以便每项任务都是在先决条件已完成的前提下逐个完成。
因为任务之间存在先决条件限制，也就是顶点之间存在方向性，所以这一类问题可以用有向无环图(DAG)来描述。如图给出一个学科学习的例子，其中必须先学完某些功课才能学习其它功课，当然也有一些比较独立的功课，例如体育课。图中有向边(u, v)表示功课u必须在功课v之前学习。所以该图的拓扑排序将可以给出一个功课学习的先后顺序。
图 功课学习先后顺序图
事实上拓扑排序是有向无环图深度优先搜索的直接应用。假设对某一有向无回路图G=(V, E)运行DFS，并确定其所有顶点的搜索完成时间f。图中某一条边(u, v) 在DFS过程中，f[u]必定大于f[v]。所以只要将图中各顶点按照DFS搜索所获得的搜索完成时间由大到小进行排序即可完成拓扑排序。
根据上面的分析，拓扑排序算法实现如下：
/** * 图的拓扑排序算法，排序后各顶点的标号按顺序排放至 * 数组，并将该数组返回。 * @param g 带排序的有向无环图 * @return 排序后顶点存放至数组 */ public static int[] topologocal_sort(GraphLnk g){ // 首先对图进行深度优先搜索 GraphSearch.DFS(g); int n = g.get_nv(); int[] f = new int[n]; // 各顶点深度优先搜索时的第二个时间 for( int i = 0; i < n; i++){ f[i] = GraphSearch.f[i]; } // 创建数组，用于放置排序后各顶点的标号 int r[] = new int[n]; // 按照f值由大到小将各顶点排序 // 遍历n次 for( int i = 0; i < n; i++){ int _max = f[0], _max_idx = 0; // 每次遍历寻找f值最大的下标 for( int j = 1; j < n; j++) if(f[j] > _max){ _max = f[j]; _max_idx = j; } // 将找到的最大值重赋值为无穷小 f[_max_idx] = -Integer.MAX_VALUE; // 将序号存放置数组r r[i] = _max_idx; } return r; }
算法首先对图进行DFS搜索，并获得各顶点完成遍历的时间f。然后，将各顶点的序号逐个取出并放置到待返回的数组中。顶点取出的顺序根据顶点的f时间值由大到小决定。
图各顶点标号如图，顶点经过DFS后各顶点的搜索完成时间d[u]/f[u]为：
0)1/14
1)15/16
2)17/18
3)2/7
4)8/13
5)9/12
6)3/6
7)10/11
8)4/5
图 功课学习先后顺序对应的有向无环图
调用拓扑排序函数对该图进行拓扑排序：
// 图顶点标号对应数组中的功课名称 String course[] = {"语文", "算术", "体育","英语", "数学", "基础物理","基础物理英文", "固态物理", "固态物理英文"}; // 从文件获取图的信息 GraphLnk GL = Utilities.BulidGraphLnkFromFile("Graph\\graph5.txt"); // 对图进行拓扑排序 int od[] = TopologicalSort.topologocal_sort(GL); // 打印拓扑排序后顶点顺序 for( int i = 0; i < od.length; i++){ System.out.print(od[i] + ". " + course[od[i]]+" "); }
排序后各顶点的顺序为：
2. 体育 1. 算术 0. 语文 4. 数学 5. 基础物理 7. 固态物理 3. 英语 6. 基础物理英文 8. 固态物理英文
按照这个顺序可以将图中每个顶点沿水平方向形成一个顶点序列，使得图中有向边都由左指向右。
图 图中功课学习拓扑排序结果图
拓扑排序有一个很重要的应用：在c/c++语言中，我们的工程中常常会包含很多头文件，头文件有会include别的头文件，所以这些头文件之间形成一个有向图。编译器在编译时需要确定文件的编译先后次序。aha，拓扑排序可以用来为头文件进行排序！
转载于:https://www.cnblogs.com/luweiseu/archive/2012/07/14/2591339.html
相关资源：垃圾分类数据集及代码