在本教程中，我们将看到图表中的拓扑排序。

拓扑排序是排序的顶点或者节点，诸如(U，V)之间存在边缘，然后U应该在拓扑分类中进行v。
仅针对导向的非循环图(DAG)可能是可能的拓扑排序。
如果图表中有一个循环，那么拓扑排序不会有任何可能性。

拓扑排序示例

让我们在一个例子的帮助下了解。
我们可能已将Maven用作构建工具。
如果我们在Maven中有多个模块，则基于依赖项的Maven构建项目。
让我们说你有4个maven模块。

• Maven-Model.
• Maven-Business-Logic
• Mavan-ilil.
• Maven-UI.

现在，我们需要在Maven-Business-Logic之前构建Maven-Model，因为Maven-Business-Logic使用Maven-Model的代码。
如Simiriarly，Maven-Model，Maven-Business-Logic和Maven-Util应该在Maven-UI之前构建，因为Maven-UI取决于所有三个模块。

因此，在这种情况下，我们可以计算拓扑排序，以便Maven可以以正确的顺序构建它们。

拓扑排序算法

请注意，拓扑排序可能有多个解决方案。

让我们在这里拾取节点30。

• 节点30取决于节点20和节点10.
• 节点10取决于节点20和节点40。
• 节点20取决于节点40。

因此，节点10，节点20和节点40应该在节点30之前拓扑分类。

该算法是深度首先搜索的变体。

在第一次搜索中，我们首先打印顶点，然后转到其邻居，但在拓扑排序的情况下，我们不立即打印顶点，而是将其推向堆栈。

在拓扑分类中，我们将有一个临时堆栈。
我们不会立即打印顶点，我们首先递归地称呼所有邻居顶点的拓扑排序，然后将其推向堆叠。
我们将在使用递归顶部排序完成后打印堆栈。

为什么它有效？

它有效，因为当我们将任何节点推到堆栈时，我们已经推出了邻居(以及他们的邻居等)，因此没有任何依赖性的节点将位于堆栈的顶部。
在我们的情况下，我们将在堆栈的顶部有40个。

Java计划实现拓扑排序

package org.igi.theitroad;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
 
public class TopologicalSort
{ 
	Stack<Node> stack;
 
	public TopologicalSort() {
		stack=new Stack<>();
	}
	static class Node
	{
		int data;
		boolean visited;
		List<Node> neighbours;
 
		Node(int data)
		{
			this.data=data;
			this.neighbours=new ArrayList<>();
 
		}
		public void addneighbours(Node neighbourNode)
		{
			this.neighbours.add(neighbourNode);
		}
		public List<Node> getNeighbours() {
			return neighbours;
		}
		public void setNeighbours(List<Node> neighbours) {
			this.neighbours = neighbours;
		}
		public String toString()
		{
			return ""+data;
		}
	}
 
	//Recursive toplogical Sort
	public  void toplogicalSort(Node node)
	{
		List<Node> neighbours=node.getNeighbours();
		for (int i = 0; i < neighbours.size(); i++) {
			Node n=neighbours.get(i);
			if(n!=null && !n.visited)
			{
				toplogicalSort(n);
				n.visited=true;
			}
		}
		stack.push(node);
	}
 
	public static void main(String arg[])
	{
 
		TopologicalSort topological = new TopologicalSort();
		Node node40 =new Node(40);
		Node node10 =new Node(10);
		Node node20 =new Node(20);
		Node node30 =new Node(30);
		Node node60 =new Node(60);
		Node node50 =new Node(50);
		Node node70 =new Node(70);
 
		node40.addneighbours(node10);
		node40.addneighbours(node20);
		node10.addneighbours(node30);
		node20.addneighbours(node10);
		node20.addneighbours(node30);
		node20.addneighbours(node60);
		node20.addneighbours(node50);
		node30.addneighbours(node60);
		node60.addneighbours(node70);
		node50.addneighbours(node70);
 
		System.out.println("Topological Sorting Order:");
		topological.toplogicalSort(node40);
		
		//Print contents of stack
		Stack<Node> resultStack=topological.stack;
		while (resultStack.empty()==false)
			System.out.print(resultStack.pop() + " ");
	}
 
}

运行上面的程序时，我们将得到以下输出：

Topological Sorting Order:
40 20 50 10 30 60 70

时间复杂性

与另外的堆栈相似，非常类似于深度搜索。
所以它的时间复杂性是O(v + e)。