图解拓扑排序（Topological sort)

川长思鸟来 2022-04-04 03:19 190阅读 0赞

### 一、什么是拓扑排序 ###

下图就是拓扑排序

![th_id_OIP.nxElBe95mxRP0b4rFctKvQHaEx_pid_Api][]

拓扑排序其实是一个线性排序。——若图中存在一条有向边从*u*指向*v*，则在拓扑排序中*u*一定出现在*v*前面。

[维基百科拓扑排序的定义][Link 1]：

a **topological sort** or **topological ordering** of a [directed graph][] is a [linear ordering][] of its [vertices][] such that for every directed edge *uv* from vertex *u* to vertex *v*, *u*comes before *v* in the ordering.

### 二、图解拓扑排序 ###

算法思路：

1. 从图中选择一个没有前驱（即入度为0）的顶点并输出。  
2. 从图中删除该顶点和所有以它为起点的有向边。  
重复 1 和 2 直到图为空或当前图中不存在无前驱的顶点为止。

伪码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70][]

例子：

![th_id_OIP.nxElBe95mxRP0b4rFctKvQHaEx_pid_Api][]

. 1.  选入度为0的节点A，  输出A。  删除AB AC的边（B入度为1-1=0，C入度为2-1=1）

2.  选入度为0的节点B， 输出B。删除BC，BE的边（C入度为1-1=0，E入度-1）

3.   选入度为0的节点C， 输出C。删以C开始的边（对应节点入度-1）

。。。。。。。。。。。继续重复。。。。。。。。。。

注： 拓扑排序结果不唯一（同时有多个入度为0）。

### 三、Code in Java ###

import java.util.*;
    
    // data structure to store graph edges
    class Edge
    {
    	int source, dest;
    
    	public Edge(int source, int dest) {
    		this.source = source;
    		this.dest = dest;
    	}
    };
    
    // class to represent a graph object
    class Graph
    {
    	// An array of Lists to represent adjacency list
    	List<List<Integer>> adjList = null;
    
    	// stores indegree of a vertex
    	List<Integer> indegree = null;
    
    	// Constructor
    	Graph(List<Edge> edges, int N) {
    		adjList = new ArrayList<>(N);
    		for (int i = 0; i < N; i++) {
    			adjList.add(i, new ArrayList<>());
    		}
    
    		// initialize indegree of each vertex by 0
    		indegree = new ArrayList<>(Collections.nCopies(N, 0));
    
    		// add edges to the undirected graph
    		for (int i = 0; i < edges.size(); i++)
    		{
    			int src = edges.get(i).source;
    			int dest = edges.get(i).dest;
    
    			// add an edge from source to destination
    			adjList.get(src).add(dest);
    
    			// increment in-degree of destination vertex by 1
    			indegree.set(dest, indegree.get(dest) + 1);
    		}
    	}
    }
    
    class Main
    {
    	// performs Topological Sort on a given DAG
    	public static List<Integer> doTopologicalSort(Graph graph, int N)
    	{
    		// list to store the sorted elements
    		List<Integer> L = new ArrayList<>();
    
    		// get indegree information of the graph
    		List<Integer> indegree = graph.indegree;
    
    		// Set of all nodes with no incoming edges
    		Stack<Integer> S = new Stack<>();
    		for (int i = 0; i < N; i++) {
    			if (indegree.get(i) == 0) {
    				S.add(i);
    			}
    		}
    
    		while (!S.isEmpty())
    		{
    			// remove a node n from S
    			int n = S.pop();
    
    			// add n to tail of L
    			L.add(n);
    
    			for (int m : graph.adjList.get(n))
    			{
    				// remove edge from n to m from the graph
    				indegree.set(m, indegree.get(m) - 1);
    
    				// if m has no other incoming edges then
    				// insert m into S
    				if (indegree.get(m) == 0) {
    					S.add(m);
    				}
    			}
    		}
    
    		// if graph has edges then graph has at least one cycle
    		for (int i = 0; i < N; i++) {
    			if (indegree.get(i) != 0) {
    				return null;
    			}
    		}
    
    		return L;
    	}
    
    	public static void main(String[] args)
    	{
    		// vector of graph edges as per above diagram
    		List<Edge> edges = Arrays.asList(
    							new Edge(0, 6), new Edge(1, 2), new Edge(1, 4),
    							new Edge(1, 6), new Edge(3, 0), new Edge(3, 4),
    							new Edge(5, 1), new Edge(7, 0), new Edge(7, 1)
    						);
    
    		// Set number of vertices in the graph
    		final int N = 8;
    
    		// create a graph from edges
    		Graph graph = new Graph(edges, N);
    
    		// Perform Topological Sort
    		List<Integer> L = doTopologicalSort(graph, N);
    
    		if (L != null) {
    			System.out.print(L);	// print topological order
    		} else {
    			System.out.println("Graph has at least one cycle. " +
    							 "Topological sorting is not possible");
    		}
    	}
    }

### 四、算法分析 ###

时间复杂度： `O(n + e)`，其中`n`为图中的结点数目，`e`为图中的边的数目

空间复杂度：`O(n)`

也可以用深度优先遍历DFS和 广度优先遍历BFS 实现拓扑排序。

`  `

## ##

[th_id_OIP.nxElBe95mxRP0b4rFctKvQHaEx_pid_Api]: https://tse3.mm.bing.net/th?id=OIP.nxElBe95mxRP0b4rFctKvQHaEx&pid=Api
[Link 1]: https://en.wikipedia.org/wiki/Topological_sorting
[directed graph]: https://en.wikipedia.org/wiki/Directed_graph
[linear ordering]: https://en.wikipedia.org/wiki/Total_order
[vertices]: https://en.wikipedia.org/wiki/Vertex_%28graph_theory%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70]: /images/20220404/47c2401634874910aed4b6648fcc86a9.png