【算法】基于AOV网的拓扑排序

今天药忘吃喽~ 2022-06-08 07:22 304阅读 0赞

写在前面：这篇文章在一周前就应该发的，后来因为腾讯面试拖到现在，虽然现在下动车也有一两个小时了，但是感觉自己好像还在路上颠簸。昨天去腾讯深圳总部面试，深圳总部啊！马爸爸在的地方！可惜跪了。可能是因为我主要偏软件开发然后投了运维简历投偏了吧，腾讯的面试还真是玄学呢！我也感受到自己已经达到了技术瓶颈，回炉修炼~

图的这一章节终于快复习完了，加油加油！今天要总结的是拓扑排序，是基于AOV网的。这个拓扑排序与我们之前熟知的快速排序啊，冒泡排序啊有异同点。相同的地方是它们都能把一组数排序成有序序列。而不同的地方也恰恰在这个有序上，拓扑排序中的有序并不是什么从大到小，或者是从小到大；而是一种先后的逻辑上的关系，具有一定的实际意义。

知识储备：AOV网

AOV网是一个英文缩写，全称是Activity On Vertex Network，即活动在顶点上的网。是一个**有向不带权重的图，并且没有回路**。可以用它来描述工程中各个活动的先后次序，如工业上的流程，如下图

![20170919085948464][]

要制作一个产品，首先要去寻找原料，然后生成出3个部件，最后获得成品。这个就是一个普通的生产过程，如果我们用一条有向线段从成品指向了原料，那么这个图中就出现了回路，也就是出现环了。这样的话，刚生产出来的产品却又变成了原料，这显然是违背【生产产品】这个工程的实际意义的。

拓扑排序看上去很抽象，其实实现起来还是十分容易的。算法思路如下：

1、      选择图中入度为0的顶点，输出

2、      删除这个顶点引出的所有边

3、      重复步骤【1】、【2】，直到图中所有顶点输出为止(也就是不再有入度为0的点)

算法准备：

1、      图的邻接矩阵存储结构(其实用邻接表也是可以的)

2、      一个visit数组，用于标识某个顶点是否被输出过

下面先用手工的方式演示一下拓扑排序的算法过程(基于邻接矩阵)

![20170924203620729][]

我们的用例图如A所示，邻接矩阵在右下角，图的顶点编号从1开始。

1、初始化visit数组，默认全为0

![20170924204028417][]

2、 我们知道，在图的邻接矩阵存储结构中，每一行之和代表这个顶点的出度，每一列之和代表一个顶点的入度。所以，我们选择邻接矩阵中第一次出现的，列和全为0的点，显然是编号为1的顶点。将visit\[1\]的值改为1，并且将这个顶点输出。

![20170924204407984][]

3、 删除顶点1，以及顶点1引出的所有边(出度)，这样，就由图A变为图B。对应的矩阵操作就是将第1行全变为0

4、继续寻找邻接矩阵中列和为0的点，此时图中第1列和第2列都是符合条件的，但是顶点1已经访问过了，所以选择顶点2，即第二列。将visit\[2\]的值改为1，并输出

![20170924204505943][]

5、删除顶点2以及它所引出的边，即将邻接矩阵中第2行全变为0。由图B变为图C

6、 如此往复，直到visit数组全变为1为止。

最后输出序列为：1 2 3 4 5

需要注意的是，拓扑排序的序列不是唯一的，我这边是采用数组，如果采用栈的话就不一定是这个序列了。

拓扑排序的要求是图不能有回路，如果图中带环，会导致排序失败，因为图会在某一个时刻找不到入度为0的点，所以拓扑排序的一个应用是检测图中是否带有回路。

下面上代码：这段代码带有图是否有环的检测

1、图的结构体定义(n为顶点数、e为边数)

#define Max 100
    typedef struct graph *Graph;
    typedef struct graph
    {
    	int data[Max][Max];
    	int n , e;
    }graph;
    //data表示邻接矩阵，最大100 x 100
    //n表示图有n个顶点，e表示有e条边

2、拓扑排序代码(邻接矩阵+数组实现)

int TopSort(Graph g)
    {
    	int v , i , j , count , n = 0;
    	int *visit = (int*)malloc(sizeof(int) * (g->n + 1));
        //初始化visit数组
    	for(i = 1 ; i <= g->n ; i++)
    	{
    		visit[i] = 0;
    	}
    	while(n != g->n)
    	{
            //遍历邻接矩阵，寻找入度为0的点，若找到，退出循环
    		for(i = 1 ; i <= g->n ; i++)
    		{
    			count = 0;
    			for(j = 1 ; j <= g->n ; j++)
    			{
    				count += g->data[j][i];
    			}
    			if(count == 0 && visit[i] == 0)
    			{
    				v = i;
    				n++;
    				visit[v] = 1;
    				break;
    			}
    		}
    		//如果某一时刻遍历完全部的邻接矩阵也没有找到入度为0的点
            //此时，i与j指向最后一个元素，势必相等，表示发现环。
    		if(i == j)//发现环
    		{
    			return 1;
    		}
    		
    		printf("%d ",v);
    		
            //将入度为0的点v所在的那一行全部变成0，因为列已经全0，表示删除该点
    		for(i = 1 ; i <= g->n ; i++)
    		{
    			g->data[v][i] = 0;
    		}
    	}
    	return 0;
    }

最后附上一张腾讯招聘现场吧~勉励自己继续加油！

![20170924222601512][]

[20170919085948464]: /images/20220608/4cf6f8f89c9d43199e3f2d2f36e8aaea.png
[20170924203620729]: /images/20220608/fe205d06f8474c4e8053a738dd3ada90.png
[20170924204028417]: /images/20220608/7bd20b6494a14b6caffe40f36f725d99.png
[20170924204407984]: /images/20220608/123b1621dbcf48f586063291de392cbc.png
[20170924204505943]: /images/20220608/24716ea94b44441fb3193387fa8bbabb.png
[20170924222601512]: /images/20220608/f0d0b045ec3c4f4f8fbbad8386a58044.png