前言
在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础，学习ssm框架前要掌握jsp/servlet之类才行。
为了简化问题，我们使用整数为顶点编号的标准模型来表示这个案例：
此时如果某个同学要学习这些课程，就需要指定出一个学习的方案，我们只需要对图中的顶点进行排序，让它转换为一个线性序列，就可以解决问题，这时就需要用到一种叫拓扑排序的算法。
拓扑排序介绍
给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图:
检测有向图中的环
如果学习x课程前必须先学习y课程，学习y课程前必须先学习z课程，学习z课程前必须先学习x课程，那么一定是有问题了，我们就没有办法学习了，因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环：
因此，如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。
实现思路
在API中添加了onStack[] 布尔数组，索引为图的顶点，当我们深度搜索时：
- 在如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；
- 如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；
- 如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；
API设计
| 类名 | DirectedCycle |
| 成员变量 | 1.private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索2.private boolean hasCycle: 记录图中是否有环3.private boolean[] onStack:索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上 |
| 构造方法 | DirectedCycle(Digraph G)：创建一个检测环对象，检测图G中是否有环 |
| 成员方法 | 1.private void dfs(Digraph G,int v)：基于深度优先搜索，检测图G中是否有环2.public boolean hasCycle():判断图中是否有环 |
代码实现
/** * 有向图是否存在环 * * @author alvin * @date 2022/11/2 * @since 1.0 **/ public class DirectedCycle { //索引代表顶点，值表示当前顶点是否已经被搜索 private boolean[] marked; //记录图中是否有环 private boolean hasCycle; //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上 private boolean[] onStack; //创建一个检测环对象，检测图G中是否有环 public DirectedCycle(Digraph G){ //初始化marked数组 this.marked = new boolean[G.V()]; //初始化hasCycle this.hasCycle = false; //初始化onStack数组 this.onStack = new boolean[G.V()]; //找到图中每一个顶点，让每一个顶点作为入口，调用一次dfs进行搜索 for (int v =0; v<G.V();v++){ //判断如果当前顶点还没有搜索过，则调用dfs进行搜索 if (!marked[v]){ dfs(G,v); } } } //基于深度优先搜索，检测图G中是否有环 private void dfs(Digraph G, int v){ //把顶点v表示为已搜索 marked[v] = true; //把当前顶点进栈 onStack[v] = true; for(Integer w: G.adj(v)) { //判断如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索 if(!marked[w]) { dfs(G, w); } //判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了 if (onStack[w]){ hasCycle = true; return; } } //把当前顶点出栈 onStack[v] = false; } //判断当前有向图G中是否有环 public boolean hasCycle(){ return hasCycle; } }
基于深度优先的顶点排序
实现思路
如果要把图中的顶点生成线性序列其实是一件非常简单的事，之前我们学习并使用了多次深度优先搜索，我们会发现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。
我们添加了一个栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。
API设计
| 类名 | DepthFirstOrder |
| 成员变量 | 1.private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索2.private Stack reversePost: 使用栈，存储顶点序列 |
| 构造方法 | DepthFirstOrder(Digraph G)：创建一个顶点排序对象，生成顶点线性序列； |
| 成员方法 | 1.private void dfs(Digraph G,int v)：基于深度优先搜索，生成顶点线性序列2.public Stack reversePost():获取顶点线性序列 |
代码实现
/** * 顶点排序 * * @author alvin * @date 2022/11/2 * @since 1.0 **/ public class DepthFirstOrder { //索引代表顶点，值表示当前顶点是否已经被搜索 private boolean[] marked; //使用栈，存储顶点序列 private Stack<Integer> reversePost; //创建一个检测环对象，检测图G中是否有环 public DepthFirstOrder(Digraph G){ //初始化marked数组 this.marked = new boolean[G.V()]; //初始化reversePost栈 this.reversePost = new Stack<>(); //遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索 for (int v = 0;v<G.V();v++){ if (!marked[v]){ dfs(G,v); } } } //基于深度优先搜索，把顶点排序 private void dfs(Digraph G, int v){ //标记当前v已经被搜索 marked[v] = true; //通过循环深度搜索顶点v for (Integer w : G.adj(v)) { //如果当前顶点w没有搜索，则递归调用dfs进行搜索 if (!marked[w]){ dfs(G,w); } } //让顶点v进栈 reversePost.push(v); } //获取顶点线性序列 public Stack<Integer> reversePost(){ return reversePost; } }
拓扑排序
前面已经实现了环的检测以及顶点排序，那么拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可。
API设计
| 类名 | TopoLogical |
| 成员变量 | 1.private Stack order: 顶点的拓扑排序 |
| 构造方法 | TopoLogical(Digraph G)：构造拓扑排序对象 |
| 成员方法 | 1.public boolean isCycle()：判断图G是否有环2.public Stack order():获取拓扑排序的所有顶点 |
代码实现
/** * 拓扑排序 * * @author alvin * @date 2022/11/2 * @since 1.0 **/ public class TopoLogical { //顶点的拓扑排序 private Stack<Integer> order; //构造拓扑排序对象 public TopoLogical(Digraph G) { //创建一个检测有向环的对象 DirectedCycle cycle = new DirectedCycle(G); //判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象 if (!cycle.hasCycle()){ DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G); order = depthFirstOrder.reversePost(); } } //判断图G是否有环 private boolean isCycle(){ return order==null; } //获取拓扑排序的所有顶点 public Stack<Integer> order(){ return order; } }
测试验证
public class TopoLogicalTest { @Test public void test() { //准备有向图 Digraph digraph = new Digraph(6); digraph.addEdge(0,2); digraph.addEdge(0,3); digraph.addEdge(2,4); digraph.addEdge(3,4); digraph.addEdge(4,5); digraph.addEdge(1,3); //通过TopoLogical对象堆有向图中的顶点进行排序 TopoLogical topoLogical = new TopoLogical(digraph); //获取顶点的线性序列进行打印 Stack<Integer> order = topoLogical.order(); StringBuilder sb = new StringBuilder(); while (order.size() != 0) { sb.append(order.pop()+"->"); }; String str = sb.toString(); int index = str.lastIndexOf("->"); str = str.substring(0,index); System.out.println(str); } }
