【拓扑排序（Topological Sorting）——图】

Bertha 。 2022-12-21 06:09 205阅读 0赞

### 拓扑排序（Topological Sorting） ###

*  一、基本概念
 *  二、拓扑排序的过程
 *  三、拓扑排序的实现
 *   *   *  1、设计数据结构
         *  2、实现拓扑排序

**前言：  
对一项工程，我们最关心两个问题：  
1、工程能否顺利完成；\{拓扑排序）  
2、整个工程完成所必需的最短工期;（关键路径）**

# 一、基本概念 #

**1、有向无环图：无环的有向图，简称DAG图（directed acycling graph）  
作用：用来描述一项工程或者系统的进行过程。通常把计划、施工、生产、程序流程等当成一个工程。一个工程都可以分成若干子工程（称为活动）。要完成整个工程，就要完成所有活动。而活动的执行通常是有某些先决条件的，即一些活动必须先于另一些活动完成。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

**2、AOV网：用一个有向图表示一个工程的各子工程及其相互制约关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网。**

**3、AOV网的特点：  
（1）若从i到j有一条有向路径，则i是j的前驱，j是i的后继  
（2）若<i,j>是网中有向边，则i是j的直接前驱，j是i的直接后继  
（3）AOV网中不应该有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是不符合逻辑的  
（4）AOV网应该是一个有向无环图，即DAG图**

![在这里插入图片描述][202011151316550.png_pic_center]  
**4、拓扑排序（可以判断一个有向图是否存在环）：就是将AOV网中所有顶点排成一个线性序列（称为拓扑序列），该序列满足：  
若在AOV网中由顶点vi到vj有一条路径，则在该线性序列中的顶点vi必定在vj之前。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

> 拓扑排序可以用来测试AOV网是否有环：  
> 1若网中所有顶点都在它的拓扑排序序列中，则该AOV网中必定不存在环。  
> 2、如果有向图存在环，则不能进行拓扑排序；反之，如果对一个有向图不能进行拓扑排序，则必定存在环。

# 二、拓扑排序的过程 #

**1、在有向图中选一个无前驱的顶点且输出它（即入度为0）**  
**2、从图中删除该顶点和所有以它为起点的边  
3、重复1、2，直至不存在无前驱的顶点  
4、若此时输出的顶点数小于有向图的顶点数，则说明有向图存在环，否则输出的顶点序列为一个拓扑序列。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

> 1、图空：拓扑排序成功  
> 2、图不空，但找不到无前驱的顶点：有环
> 
> 拓扑排序的两个基本操作：  
> 1、计算每个顶点的入度：计算直接前驱个数  
> 2、删除顶点所有的出边：将该顶点的邻接点的入度-1

# 三、拓扑排序的实现 #

### 1、设计数据结构 ###

**主要的存储结构：以邻接表存储有向图，因为删除边用邻接表比邻接矩阵更有效。**

**辅助的存储结构：  
（1）一维数组indegree\[i\]:存放各顶点入度，主要用于删除顶点，使得弧头入度-1  
（2）栈S：暂存所有入度为0的顶点，避免重复扫描数组indegree检测入度为0的顶点，提高算法效率  
（3）一维数组topo\[i\]:记录拓扑序列的顶点序号**

### 2、实现拓扑排序 ###

**（1）、算法思想：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]  
**（2）、算法描述：**

Status TopologicalSort(ALGraph G, int topo[])
    {
        	//有向图G采用邻接表存储
    	//若G无回路，则生成G的一个拓扑序列topo[]并返回OK,否找ERROR
    	FindInDegree(G,indegree);			//求出各顶点的入度存入数组indegree中
    	InitStack(S);			//栈初始化为空
    	for (i = 0i < G.vexnum;++i)
    		if (!indegree[i]) Push(S, i);			//入度为0者进栈
    	m = 0;			//对输出顶点计数，初始化为0
    	while (!StackEmpty(S))			//栈S非空
    	{
        
    		Pop(S, i);			//取栈顶顶点vi出栈
    		topo[m] = i;		//将vi保存在拓扑序列数组topo中
    		++m;			//对输出顶点计数
    		p = G.vertices[i].firstarc;			//p指向vi的第一个邻接点
    		while (p)
    		{
        
    			k = p->adjvex;			//vk为vi的邻接点
    			--indegree[k];			//vi的每个邻接点的入度-1
    			if (indegree[k] == 0)
    				Push(S, k);			//若入度减为0，则入栈
    			p = p->nextarc;			//p指向顶点vi的下一个邻接点
    		}
    	}
    	if (m < G.vexnum)
    		return ERROR;			//该有向图有回路
    	else
    		return OK;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/19f982f3ea29403ba9ae210d83006f4c.png
[202011151316550.png_pic_center]: /images/20221120/5a9cfe2f3965440b9dd43ea084ddfd85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b48da0f770064a55b88a32db97cf18f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/fd3b15499c494a859607522840f4b12b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/b70124869dd8474197c351c54d991d48.png