拓扑排序的java代码实现过程详解

清疚 2023-09-23 20:37 90阅读 0赞

# 拓扑排序 #

> 在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础，学习ssm框架前要掌握jsp/servlet之类才行。  
> ![在这里插入图片描述][eb7b6b01a9e64c18bfacffdf3fef829d.png]  
> ![在这里插入图片描述][351a032c933e4efba2053d9f1d1b66d0.png]

> **定义：**  
> 给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明  
> 确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图：  
> ![在这里插入图片描述][5be29a51333e4241aebbb7bfda82c1d8.png]

# 1.检测有向图中的环 #

![在这里插入图片描述][db8683dcfe7e4dcca6ea029d332b64c4.png]

## 1.1 API设计 ##

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>DirectedCycle</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td>DirectedCycle(Digraph G)：创建一个检测环对象，检测图G中是否有环</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.private void dfs(Digraph G,int v)：基于深度优先搜索，检测图G中是否有环<br>2.public boolean hasCycle():判断图中是否有环</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索<br>2.private boolean hasCycle: 记录图中是否有环<br>3.private boolean[] onStack:索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上</td> 
  </tr> 
 </tbody> 
</table>

> 在API中添加了onStack\[\] 布尔数组，索引为图的顶点，当我们深度搜索时：
> 
> 1.  在如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；
> 2.  如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；
> 3.  如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；

![在这里插入图片描述][8d2c8f4324884536ab1b604ca43a0f07.png]  
![在这里插入图片描述][bff176173def46e68bb35def14a362ef.png]

## 1.1 代码实现 ##

public class DirectedCycle {
        
    	//索引代表顶点，值表示当前顶点是否已经被搜索
    	private boolean[] marked;
    	//记录图中是否有环
    	private boolean hasCycle;
    	//索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    	private boolean[] onStack;
    	//创建一个检测环对象，检测图G中是否有环
    	public DirectedCycle(Digraph G){
        
    		//创建一个和图的顶点数一样大小的marked数组
    		marked = new boolean[G.V()];
    		//创建一个和图的顶点数一样大小的onStack数组
    		onStack = new boolean[G.V()];
    		//默认没有环
    		this.hasCycle=false;
    		//遍历搜索图中的每一个顶点
    		for (int v = 0; v <G.V(); v++) {
        
    			//如果当前顶点没有搜索过，则搜索
    			if (!marked[v]){
        
    			dfs(G,v);
    			}
    		}
    	}
    	//基于深度优先搜索，检测图G中是否有环
    	private void dfs(Digraph G, int v){
        
    		//把当前顶点标记为已搜索
    		marked[v]=true;
    		//让当前顶点进栈
    		onStack[v]=true;
    		//遍历v顶点的邻接表，得到每一个顶点w
    		for (Integer w : G.adj(v)){
        
    			//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
    			if (!marked[w]){
        
    				dfs(G,w);
    			}
    		//如果顶点w已经被搜索过，则查看顶点w是否在栈中，如果在，则证明图中有环，修改hasCycle标记，结束循环
    			if (onStack[w]){
        
    				hasCycle=true;
    				return;
    			}
    		}
    		//当前顶点已经搜索完毕，让当前顶点出栈
    		onStack[v]=false;
    	}
    	//判断w顶点与s顶点是否相通
    	public boolean hasCycle(){
        
    		return hasCycle;
    	}
    }

# 2.基于深度优先的顶点排序 #

> 如果要把图中的顶点生成线性序列其实是一件非常简单的事，之前我们学习并使用了多次深度优先搜索，我们会发现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。

## 2.1 顶点排序API设计 ##

![在这里插入图片描述][c120a90d68174865a667f440b2772b5d.png]

> 在API的设计中，我们添加了一个栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。

![在这里插入图片描述][7cb13256d66b4a649fcade7ac4002211.png]  
![在这里插入图片描述][34e64af33b8d48f9b17322227c67e42f.png]  
![在这里插入图片描述][b0ef75bade0942e2ac9a9c9188a66b87.png]

## 2.2 代码实现过程 ##

public class DepthFirstOrder {
        
    	//索引代表顶点，值表示当前顶点是否已经被搜索
    	private boolean[] marked;
    	//使用栈，存储顶点序列
    	private Stack<Integer> reversePost;
    	//创建一个检测环对象，检测图G中是否有环
    	public DepthFirstOrder(Digraph G){
        
    		//创建一个和图的顶点数一样大小的marked数组
    		marked = new boolean[G.V()];
    		reversePost = new Stack<Integer>();
    		//遍历搜索图中的每一个顶点
    		for (int v = 0; v <G.V(); v++) {
        
    			//如果当前顶点没有搜索过，则搜索
    			if (!marked[v]){
        
    				dfs(G,v);
    			}
    		}
    	}
    	//基于深度优先搜索，检测图G中是否有环
    	private void dfs(Digraph G, int v){
        
    		//把当前顶点标记为已搜索
    		marked[v]=true;
    		//遍历v顶点的邻接表，得到每一个顶点w
    		for (Integer w : G.adj(v)){
        
    		//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
    			if (!marked[w]){
        
    				dfs(G,w);
    			}
    		}
    		//当前顶点已经搜索完毕，让当前顶点入栈
    		reversePost.push(v);
    	}
    	//获取顶点线性序列
    	public Stack<Integer> reversePost(){
        
    		return reversePost;
    	}
    }

# 3.拓扑排序 #

前面已经实现了环的检测以及顶点排序，那么拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，  
则调用顶点排序即可。

## 3.1 API设计 ##

![在这里插入图片描述][6bece8ad8db345568de4f78748cab8e1.png]

## 3.2 代码实现 ##

public class TopoLogical {
        
    	//顶点的拓扑排序
    	private Stack<Integer> order;
    	//构造拓扑排序对象
    	public TopoLogical(Digraph G) {
        
    		//创建检测环对象，检测图G中是否有环
    		DirectedCycle dCycle = new DirectedCycle(G);
    		if (!dCycle.hasCycle()){
        
    		//如果没有环，创建顶点排序对象，进行顶点排序
    			DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
    			order = depthFirstOrder.reversePost();
    		}
    	}
    	//判断图G是否有环
    	private boolean isCycle(){
        
    		return order==null;
    	}
    	//获取拓扑排序的所有顶点
    	public Stack<Integer> order(){
        
    		return order;
    	}
    	
    	public class DepthFirstOrder {
        
    		//索引代表顶点，值表示当前顶点是否已经被搜索
    		private boolean[] marked;
    		//使用栈，存储顶点序列
    		private Stack<Integer> reversePost;
    		//创建一个检测环对象，检测图G中是否有环
    		public DepthFirstOrder(Digraph G){
        
    			//创建一个和图的顶点数一样大小的marked数组
    			marked = new boolean[G.V()];
    			reversePost = new Stack<Integer>();
    			//遍历搜索图中的每一个顶点
    			for (int v = 0; v <G.V(); v++) {
        
    				//如果当前顶点没有搜索过，则搜索
    				if (!marked[v]){
        
    					dfs(G,v);
    				}
    			}
    		}
    		//基于深度优先搜索，检测图G中是否有环
    		private void dfs(Digraph G, int v){
        
    			//把当前顶点标记为已搜索
    			marked[v]=true;
    			//遍历v顶点的邻接表，得到每一个顶点w
    			for (Integer w : G.adj(v)){
        
    			//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
    				if (!marked[w]){
        
    					dfs(G,w);
    				}
    			}
    			//当前顶点已经搜索完毕，让当前顶点入栈
    			reversePost.push(v);
    		}
    		//获取顶点线性序列
    		public Stack<Integer> reversePost(){
        
    			return reversePost;
    		}
    	}
    	public class DirectedCycle {
        
    		//索引代表顶点，值表示当前顶点是否已经被搜索
    		private boolean[] marked;
    		//记录图中是否有环
    		private boolean hasCycle;
    		//索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    		private boolean[] onStack;
    		//创建一个检测环对象，检测图G中是否有环
    		public DirectedCycle(Digraph G){
        
    			//创建一个和图的顶点数一样大小的marked数组
    			marked = new boolean[G.V()];
    			//创建一个和图的顶点数一样大小的onStack数组
    			onStack = new boolean[G.V()];
    			//默认没有环
    			this.hasCycle=false;
    			//遍历搜索图中的每一个顶点
    			for (int v = 0; v <G.V(); v++) {
        
    				//如果当前顶点没有搜索过，则搜索
    				if (!marked[v]){
        
    				dfs(G,v);
    				}
    			}
    		}
    		//基于深度优先搜索，检测图G中是否有环
    		private void dfs(Digraph G, int v){
        
    			//把当前顶点标记为已搜索
    			marked[v]=true;
    			//让当前顶点进栈
    			onStack[v]=true;
    			//遍历v顶点的邻接表，得到每一个顶点w
    			for (Integer w : G.adj(v)){
        
    				//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
    				if (!marked[w]){
        
    					dfs(G,w);
    				}
    			//如果顶点w已经被搜索过，则查看顶点w是否在栈中，如果在，则证明图中有环，修改hasCycle标记，结束循环
    				if (onStack[w]){
        
    					hasCycle=true;
    					return;
    				}
    			}
    			//当前顶点已经搜索完毕，让当前顶点出栈
    			onStack[v]=false;
    		}
    		//判断w顶点与s顶点是否相通
    		public boolean hasCycle(){
        
    			return hasCycle;
    		}
    	}
    
    }

参考：黑马程序员Java数据结构与java算法

[eb7b6b01a9e64c18bfacffdf3fef829d.png]: https://img-blog.csdnimg.cn/eb7b6b01a9e64c18bfacffdf3fef829d.png
[351a032c933e4efba2053d9f1d1b66d0.png]: https://img-blog.csdnimg.cn/351a032c933e4efba2053d9f1d1b66d0.png
[5be29a51333e4241aebbb7bfda82c1d8.png]: https://img-blog.csdnimg.cn/5be29a51333e4241aebbb7bfda82c1d8.png
[db8683dcfe7e4dcca6ea029d332b64c4.png]: https://img-blog.csdnimg.cn/db8683dcfe7e4dcca6ea029d332b64c4.png
[8d2c8f4324884536ab1b604ca43a0f07.png]: https://img-blog.csdnimg.cn/8d2c8f4324884536ab1b604ca43a0f07.png
[bff176173def46e68bb35def14a362ef.png]: https://img-blog.csdnimg.cn/bff176173def46e68bb35def14a362ef.png
[c120a90d68174865a667f440b2772b5d.png]: https://img-blog.csdnimg.cn/c120a90d68174865a667f440b2772b5d.png
[7cb13256d66b4a649fcade7ac4002211.png]: https://img-blog.csdnimg.cn/7cb13256d66b4a649fcade7ac4002211.png
[34e64af33b8d48f9b17322227c67e42f.png]: https://img-blog.csdnimg.cn/34e64af33b8d48f9b17322227c67e42f.png
[b0ef75bade0942e2ac9a9c9188a66b87.png]: https://img-blog.csdnimg.cn/b0ef75bade0942e2ac9a9c9188a66b87.png
[6bece8ad8db345568de4f78748cab8e1.png]: https://img-blog.csdnimg.cn/6bece8ad8db345568de4f78748cab8e1.png