【数据结构】什么是拓扑排序—关于图的拓扑排序

待我称王封你为后i 2023-09-26 10:26 14阅读 0赞

## **目录** ##

一、什么是拓扑排序？

二、拓扑排序：基本概念

三、拓扑排序：分析

四、拓扑排序：步骤

五、拓扑排序：实现

六、练习

--------------------

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

> 对一个[有向无环图][Link 1](Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中**所有顶点排成一个线性序列**，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个[偏序][Link 2]得到该集合上的一个[全序][Link 3]，这个操作称之为拓扑排序。

### 二、拓扑排序：基本概念 ###

问题：

1.  假设以有向图表示一个工程的施工图或程序的数据流图，则图中**不允许出现回路**。
2.  检查有向图**是否存在回路**的方法之一，是对有向图进行==拓扑排序==。**有回路，不是存在拓扑排序；没有回路，存在拓扑排序**
3.  一个无环的有向图称为有向无环图（Directed Acycline Graph），简称为DAG图。
4.  通常我们用一个有向图的顶点表示活动，边表示活动间先后关系，这样的有向图称为顶点活动网（Activity On Vertex network），简称AOV网。
    
    >  *  工程是否顺利进行
    >  *  完成整个工程所必须的最短时间
    >  *  在AOV网表示工程的施工图，若出现==环==，标明该工程的施工设计图存在问题。
    >  *  若AOV网表示的是数据流图，若出现==环==，标明存在死循环。
5.  **拓扑排序：对一个有向图构建拓扑序列的过程。**

### 三、拓扑排序：分析 ###

判断有向网是否存在有向环的一个方法：（对AOV网进行拓扑排序）

*  **构造一个包含图中所有顶点的”拓扑排序序列“。**
 *  若在AOV网中存在一条从顶点u到顶点v的弧，则在==拓扑有序序列中顶点u必然优先于顶点v==。
 *  若在AOV网中顶点u和顶点w之间没有弧，则在拓扑有序序列中，这两个顶点的先后次序关系可以==随意==

![69bc2b3e3501453f86c660c64a4bcb23.png][]

现有如下课程，并能够绘制下方有向图：

![1b2a403e7ff04c4a8d63f30a52f53505.png][]

实例1：存在拓扑序列**`abcefdgh`**，说明不存在环

![58402f99f4e34064becb800dd17c8869.png][]

实例2：不存在拓扑序列，说明存在环**`fdghf`**

![6627c1345a794430a5084e6244475376.png][]

--------------------

## 四、拓扑排序：步骤 ##

*  步骤：

> 1. 在AOV网中选择一个**没有前驱**的顶点并输出
> 
> 2. 从AOV网中删除该顶点以及从它出发的弧
> 
> 3. 重复1和2直到AOV网为空（即已输出所有的顶点），或剩余子图中不存在**没有前驱的顶点**。后一种情况说明该AOV网中存在有向环。

*  算法要考虑的问题：

> 1. “没有前驱”如何判断
> 
> 2. “删除顶点及以它为尾的弧”如何操作

*  解决方法：

> 1. 以==入度为零==作为没有前驱的量度
> 
> 2. 算法中**预设一个栈**，用于保存当前出现的入度为零的顶点
> 
> 3. 删除顶点及以它为尾的弧的这类操作，可用“弧头顶点的入度减1”的办法来替代。

![afd40c2b55ef49cfa6c45064053876cf.png][]

## 五、拓扑排序：实现 ##

*  由于拓扑排序中对图的主要操作是“**找从顶点出发的弧**”，并且AOV网在多数情况下是稀疏图，因此存储结构取==**邻接表**==为宜。

public class TopologicalSort {
       // 拓扑排序
       public static boolean topologicalSort(ALGraph G) throws Exception {
          int count = 0;// 输出定点计数
          int[] indegree = findInDegree(G);// 求各顶点入度
          LinkStack S = new LinkStack();// 建零入度顶点栈
          for (int i = 0; i < G.getVexNum(); i++)
             if (indegree[i] == 0)// 入度为0者进栈
                S.push(i);
    
          while (!S.isEmpty()) {
             int i = (Integer) S.pop(); // 栈不空 取栈顶元素
             System.out.print(G.getVex(i) + " ");// 输出V号顶点 并 计数
             ++count;
             for (ArcNode arc = G.getVexs()[i].firstArc; arc != null; arc = arc
                   .nextArc) {
                int k = arc.adjVex;
                if (--indegree[k] == 0)// 对i号顶点的每个邻接点的入度减1
                   S.push(k);// 若入度减为0，则入栈
             }
          }
          if (count < G.getVexNum())
             return false;//该有向图有回路
          else
             return true;
       }
    
       //求各顶点入度  算法6.11
       public static int[] findInDegree(ALGraph G) throws Exception {
          int[] indegree = new int[G.getVexNum()];
          for (int i = 0; i < G.getVexNum(); i++)
             for (ArcNode arc = G.getVexs()[i].firstArc; arc != null; arc = arc
                   .nextArc)
                ++indegree[arc.adjVex];// 入度增加1
          return indegree;
       }
    
       public static void main(String[] args) throws Exception {
          ALGraph G = GenerateGraph.generateALGraph();
          TopologicalSort.topologicalSort(G);
       }
    }
    
    // 调试结果：
    // v1 v2 v3 v5 v7 v4 v6 v8 v9

##  ##

*  拓扑排序算法总的时间复杂度：**O(n+e)**

## 六、练习 ##

试列出下图中，全部可能的拓扑有序序列：

![166d4a3d892f4f898663fe2f7f3dc6f8.png][]

[Link 1]: https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE/10972513?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E5%81%8F%E5%BA%8F/2439087?fromModule=lemma_inlink
[Link 3]: https://baike.baidu.com/item/%E5%85%A8%E5%BA%8F/10577699?fromModule=lemma_inlink
[69bc2b3e3501453f86c660c64a4bcb23.png]: https://img-blog.csdnimg.cn/69bc2b3e3501453f86c660c64a4bcb23.png
[1b2a403e7ff04c4a8d63f30a52f53505.png]: https://img-blog.csdnimg.cn/1b2a403e7ff04c4a8d63f30a52f53505.png
[58402f99f4e34064becb800dd17c8869.png]: https://img-blog.csdnimg.cn/58402f99f4e34064becb800dd17c8869.png
[6627c1345a794430a5084e6244475376.png]: https://img-blog.csdnimg.cn/6627c1345a794430a5084e6244475376.png
[afd40c2b55ef49cfa6c45064053876cf.png]: https://img-blog.csdnimg.cn/afd40c2b55ef49cfa6c45064053876cf.png
[166d4a3d892f4f898663fe2f7f3dc6f8.png]: https://img-blog.csdnimg.cn/166d4a3d892f4f898663fe2f7f3dc6f8.png