拓扑排序

本文主要是介绍拓扑排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

个人认为太难了，，，，随着难度的提升拓扑排序不再像初学那么简单，所以向大佬学习！link

什么是拓扑排序？

维基百科对于拓扑排序有如下定义：

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.

即：对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点 u 和 v，若存在一条有向边从 u 指向 v，则在拓扑排序中 u 一定出现在 v 前面。

拓扑排序主要用来解决有向图中的依赖解析（dependency resolution）问题。

举例来说，如果我们将一系列需要运行的任务构成一个有向图，图中的有向边则代表某一任务必须在另一个任务之前完成这一限制。那么运用拓扑排序，我们就能得到满足执行顺序限制条件的一系列任务所需执行的先后顺序。当然也有可能图中并不存在这样一个拓扑顺序，这种情况下我们无法根据给定要求完成这一系列任务，这种情况称为循环依赖（circular dependency）。

拓扑排序存在的前提

当且仅当一个有向图为有向无环图（directed acyclic graph，或称DAG）时，才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。该论断可以利用反证法被证明如下：

假设我们有一由 v_1 到 v_n 这 n 个结点构成的有向图，且图中 v_1，v_2，...，v_n 这些结点构成一个环。这即是说对于所有 1≤i<n-1，图中存在一条有向边从 v_i 指向 v_i+1。同时还存在一条从 v_n 指向 v_1 的边。假设该图存在一个拓扑排序。

那么基于这样一个有向图，显然我们可以得知对于所有 1≤i<n-1，v_i 必须在 v_i+1 之前被遍历，也就是 v_1 必须在 v_n 之前被遍历。同时由于还存在一条从 v_n 指向 v_1 的边，v_n 必须在 v_1 之前被遍历。这里出现了与我们的假设所冲突的结果。因此我们可以知道，该图存在拓扑排序的假设不成立。也就是说，对于非有向无环图而言，其拓扑排序不存在。

拓扑排序的算法和实现

拓扑排序的问题存在一个线性时间解。也就是说，若有向图中存在 n 个结点，则我们可以在 \(O(n)\) 时间内得到其拓扑排序，或在 \(O(n)\) 时间内确定该图不是有向无环图，也就是说对应的拓扑排序不存在。

例如一个有向无环图如下：

这篇关于拓扑排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！