拓扑排序

2024 年 8 月 28 日 | 阅读 10 分钟

有向图的拓扑排序或拓扑顺序是其顶点的一种线性排序，其中对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中出现在 v 之前。例如，图的顶点可以表示要完成的工作，边可以反映一项工作必须在另一项工作之前完成的要求。

在这种情况下，拓扑排序只是一个合法的任务序列。拓扑排序是一种图遍历，其中每个节点 v 仅在其所有依赖项都被访问后才被访问。如果图不包含有向循环，则它是一个有向无环图。任何 DAG 都有至少一个拓扑排序，并且存在以线性时间构建任何 DAG 的拓扑排序的技术。

拓扑排序有许多应用，特别是在排名问题中，如反馈弧集。即使 DAG 包含不连通的组件，拓扑排序也是可能的。

Java 代码

现在让我们编写一个拓扑排序的 Java 示例代码。

// A Sample Java program to print topological sorting of a Directed Acyclic Graph(DAG)
import java.io.*;
import java.util.*;
// A class named Graph is created that will represent a directed graph using adjacency list representation 
class Graph {	
	// A private variable named V of the Integer type is created that will be used to represent the number of nodes in the Directed Acyclic Graph
	private int V;
	// A private variable named adj of ArrayList type is created that will represent Adjacency List as ArrayList of ArrayList's
	private ArrayList<ArrayList<Integer> > adj;
	// A parameterized constructor is written that will be used to initialize the class variables of the Graph class
	Graph(int v)
	{
		V = v;
		adj = new ArrayList<ArrayList<Integer> >(v);
		for (int i = 0; i < v; ++i)
			adj.add(new ArrayList<Integer> ());
	}
	// Function to add an edge into the graph
	// A Function named addEdge is written that will be used to add a new edge into the Directed Acyclic Graph  
	void addEdge(int v, int w) { 
		// With the use of add() a new edge will be added into the Directed Acyclic Graph
		adj.get(v).add(w); 
	}
	// A recursive function used by topologicalSort
	// A recursive function named topologicalSortUtil is written that will be used to perform the topological sorting on the edges of the Directed Acyclic Graph
	void topologicalSortUtil(int v, boolean visited[],
							Stack<Integer>  stack)
	{
		// Mark the current node as visited.
		visited[v] = true;
		Integer i;
		// Recur for all the vertices adjacent
		// to thisvertex
		Iterator<Integer> it = adj.get(v).iterator();
		while (it.hasNext()) {
			i = it.next();
			if (!visited[i])
				topologicalSortUtil(i, visited, stack);
		}
		// Push current vertex to stack
		// which stores result
		stack.push(new Integer(v));
	}
	// The function to do Topological Sort.
	// It uses recursive topologicalSortUtil()
	// A Function named topologicalSort() is written that will be used to call the recursive function named topologicalSortUtil to sort the edges of the Directed Acyclic Graph 
	void topologicalSort()
	{
		Stack<Integer> stack = new Stack<Integer>();
		// Mark all the vertices as not visited
		boolean visited[] = new boolean[V];
		for (int i = 0; i < V; i++)
			visited[i] = false;
		// Call the recursive helper
		// function to store
		// Topological Sort starting
		// from all vertices one by one
		for (int i = 0; i < V; i++)
			if (visited[i] == false)
				topologicalSortUtil(i, visited, stack);
		// Print contents of stack
		while (stack.empty() == false)
			System.out.print(stack.pop() + " ");
	}
	// main function is written to call all the functionalities functions written above
	public static void main(String args[])
	{
		// Now, let us create a graph, and for that, we will create the edges of the Directed Acyclic Graph 
		// A Directed Acyclic Graph with six nodes is created for that an Object of the graph node is created by calling the constructor of the graph class
		Graph g = new Graph(26);
		Scanner scan = new Scanner(System.in);
		char ch;
       /*  Perform list operations  */
        do
            {
                System.out.println("Please Choose one of the Operations::");
                System.out.println("1. To create a Directed Acyclic Graph (DAG) for topological sort.");
                System.out.println("2. To print the result of the topological sort.");
                int choice = scan.nextInt();
                switch (choice)
                    {
                    case 1 :
						// A edge starting from vertex 25 and terminating at the vertex 10  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
						g.addEdge(25, 10);
						// A edge starting from vertex 25 and terminating at the vertex 0 is created by calling the addEdge() with passing these starting and terminating vertex to this function
						g.addEdge(25, 0);
						// A edge starting from vertex 20 and terminating at the vertex 0 is created by calling the addEdge() with passing these starting and terminating vertex to this function
						g.addEdge(20, 0);
						// A edge starting from vertex 20 and terminating at the vertex 5 is created by calling the addEdge() with passing these starting and terminating vertex to this function
						g.addEdge(20, 5);
						// A edge starting from vertex 10 and terminating at the vertex 15 is created by calling the addEdge() with passing these starting and terminating vertex to this function
						g.addEdge(10, 15);
						// A edge starting from vertex 15 and terminating at the vertex 5 is created by calling the addEdge() with passing these starting and terminating vertex to this function
						g.addEdge(15, 5);
                        break;
                    case 2 :
        				System.out.println("The result after topological sort of the Directed Acyclic Graph");
						g.topologicalSort();                
                        break;
                    default :
                        System.out.println("Wrong Entry\n ");
                        break;
                    }
                System.out.println("\nDo you want to continue (Type y or n)\n");
                ch = scan.next().charAt(0);
            }
        while (ch == 'Y'|| ch == 'y');		
	}
}

输出

上面的 Java 代码产生以下输出。

Please Choose one of the Operations::
1. To create a Directed Acyclic Graph (DAG) for topological sort.
2. To print the result of the topological sort.
1
Directed Acyclic Graph (DAG) created successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations::
1. To create a Directed Acyclic Graph (DAG) for topological sort.
2. To print the result of the topological sort.
2
The result after topological sort of the Directed Acyclic Graph
25  20 15 10 5  0 
Do you want to continue (Type y or n)
n

因此，在上面的 Java 代码中，我们创建了一个名为 Graph 的类，它将使用邻接表表示法来表示有向图。还编写了执行各种操作（如在图中添加新节点）的不同成员函数。编写了一个名为 topologicalSort() 的函数来执行图的拓扑排序的实际任务。topologicalSort() 函数内部调用了一个名为 topologicalSortUtil() 的递归函数，该函数包含图的拓扑排序的实际逻辑。一旦在图上执行了拓扑排序，由于拓扑操作，图的节点将被打印出来。

C++ 代码

让我们看看 C++ 代码，

// A Sample C++ program to print topological sorting of a Directed Acyclic Graph(DAG)
#include <iostream>	
#include <list>
#include <stack>
using namespace std;
// A class named Graph is created that will represent a directed graph using adjacency list representation 
class Graph {
	// A variable named V of the Integer type is created that will be used to represent the number of nodes in the Directed Acyclic Graph
	int V;
	// Pointer to an array containing adjacency listsList
	list<int>* adj;
	// A recursive function named topologicalSortUtil is written that will be used to perform the topological sorting on the edges of the Directed Acyclic Graph
	void topologicalSortUtil(int v, bool visited[],
							stack<int>& Stack);
public:
	// A parameterized constructor is written that will be used to initialize the class variables of the Graph class
	Graph(int V);
	// A Function named addEdge is written that will be used to add a new edge into the Directed Acyclic Graph  
	void addEdge(int v, int w);
	// A Function named topologicalSort() is written that will be used to call the recursive function named topologicalSortUtil to sort the edges of the Directed Acyclic Graph 
	void topologicalSort();
};
// A parameterized constructor is written that will be used to initialize the class variables of the Graph class
Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}
// A Function named addEdge is written that will be used to add a new edge into the Directed Acyclic Graph  
void Graph::addEdge(int v, int w)
{
	// Add w to v's list.
	adj[v].push_back(w);
}
// A recursive function named topologicalSortUtil is written that will be used to perform the topological sorting on the edges of the Directed Acyclic Graph
void Graph::topologicalSortUtil(int v, bool visited[],
								stack<int>& Stack)
{
	// Mark the current node as visited.
	visited[v] = true;
	// Recur for all the vertices
	// adjacent to this vertex
	list<int>::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i)
		if (!visited[*i])
			topologicalSortUtil(*i, visited, Stack);
	// Push current vertex to stack
	// which stores result
	Stack.push(v);
}
// A Function named topologicalSort() is written that will be used to call the recursive function named topologicalSortUtil to sort the edges of the Directed Acyclic Graph 
void Graph::topologicalSort()
{
	stack<int> Stack;
	// Mark all the vertices as not visited
	bool* visited = new bool[V];
	for (int i = 0; i < V; i++)
		visited[i] = false;
	// Call the recursive helper function
	// to store Topological
	// Sort starting from all
	// vertices one by one
	for (int i = 0; i < V; i++)
		if (visited[i] == false)
			topologicalSortUtil(i, visited, Stack);
	// Print contents of stack
	while (Stack.empty() == false) {
		cout << Stack.top() << " ";
		Stack.pop();
	}
}
// main function is written to call all the functionalities functions written above
int main()
{
	// Now, let us create a graph, and for that, we will create the edges of the Directed Acyclic Graph 
	Graph g(6);
	// A edge starting from vertex 5 and terminating at vertex 2  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(5, 2);
	// A edge starting from vertex 5 and terminating at the vertex 0  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(5, 0);
	// A edge starting from vertex 4 and terminating at the vertex 0  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(4, 0);
	// A edge starting from vertex 4 and terminating at the vertex 1  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(4, 1);
	// A edge starting from vertex 2 and terminating at the vertex 3  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(2, 3);
	// A edge starting from vertex 3 and terminating at the vertex 1  is created by calling the addEdge() with passing these starting and terminating vertex to this function 
	g.addEdge(3, 1);
	cout<<"Directed Acyclic Graph (DAG) created successfully.\n";
	cout << "The result of topological Sort is\n";
	g.topologicalSort();
	return 0;
}

输出

上面的 C++ 代码产生以下输出。

Directed Acyclic Graph (DAG) created successfully.
The result of topological Sort is
5 4 2 3 1 0

因此，在上面的 C++ 代码中，我们创建了一个名为 Graph 的类，它将使用邻接表表示法来表示有向图。还编写了执行各种操作（如在图中添加新节点）的不同成员函数。然后编写了一个名为 topologicalSort() 的函数来执行图的拓扑排序的实际任务。topologicalSort() 函数内部调用了一个名为 topologicalSortUtil() 的递归函数，该函数包含图的拓扑排序的实际逻辑。一旦在图上执行了拓扑排序，由于拓扑操作，图的节点将被打印出来。

拓扑排序的优点

拓扑排序主要用于根据作业的依赖关系进行调度。指令调度、电子表格中重新计算公式值时公式单元格评估的排序、逻辑综合、确定 make 文件中要执行的编译任务顺序、数据序列化以及链接器中符号依赖关系的解析都是这类应用在计算机科学中的示例。

在图中查找循环：只有有向无环图可以进行拓扑排序（DAG）。无法对循环图进行拓扑排序。
操作系统死锁检测：当一个进程等待另一个进程持有请求的资源时，就会发生死锁。
依赖解析：拓扑排序已被证明在依赖解析中非常有用。
句子排序：设 n 个文档 D={d1,d2...,dn}，文档中的句子数为 vi，其中 ∀i, vi>=1。假设随机顺序 o=[o1,....ovi] 和一组随机顺序的 vi 个句子为 {So1, So2,..., Sovi}。那么任务是找到正确的句子顺序 o*={o*1,...o*vi}。一组约束 Ci 表示 di 中每对句子之间的相对顺序，其中 |Ci|=(vi*(vi-1))/2。例如，如果一个文档有三个句子按正确顺序 s1 < s2 < s3，那么我们有三组约束 {s1 < s2, s1 < s3, s2 < s3}
句子的顺序可以用 DAG 表示。这里句子 (Si) 表示顶点，边表示句子之间的顺序。例如，如果我们在 S1 到 S2 之间有一个有向边，那么 S1 必须在 S2 之前。拓扑排序可以生成这些句子的排序（句子排序）。
关键路径分析：一种项目管理方法，称为关键路径分析。它用于确定项目应花费的时间以及每个行动对其他行动的依赖程度。一个活动之前可能有一些先行活动。在开始新活动之前，所有之前的活动都必须完成。
课程安排问题：拓扑排序已被证明在解决课程安排问题中非常有用。
其他应用，如制造工作流、数据序列化和上下文无关语法。

下一主题三叉搜索树

拓扑排序

Java 代码

C++ 代码

拓扑排序的优点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

拓扑排序

Java 代码

C++ 代码

拓扑排序的优点

相关帖子

Python 中数组轮换的块交换算法

二叉索引树范围更新和范围查询

不使用递归进行中序遍历

数据结构中矩阵中回文路径的数量

在给定数组中具有最大长度最长公共前缀的字符串对

RSS 链表

计算可被 k 整除的数组对

在给定树中查找最大的完美二叉树

根据另一个字符串定义的字母顺序对字符串数组进行排序

双向归并排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器