数据结构——图——拓扑排序算法

红太狼 2022-10-31 12:18 184阅读 0赞

## 数据结构——图——拓扑排序算法 ##

对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV 网中不存在入度为0的顶点为止。

首先我们需要确定一下这个图需要使用的数据结构。前面求最小生成树和最短路径时，我们用的都是邻接矩阵，但由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为0的顶点，我们在原来顶点表结点结构中，增加一个入度域in，结构如表7-8-1所示,其中in就是入度的数字。

![在这里插入图片描述][20210222164340611.png]  
因此对于图7-8-2的第一幅图AOV网，我们可以得到如第二幅图的邻接表数据结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
在拓扑排序算法中，涉及的结构代码如下。

typedef struct EdgeNode    /*边表结点*/
    {
        
    	int adjvex;            /*邻接点域，存储该顶点对应的下标*/
    	int weight;            /*用于存储权值，对于非网图可以不需要*/
    	struct EdgeNode* next; /*链域，指向下一个邻接点*/
    
    }EdgeNode;
    
    typedef struct VertexNode   /*顶点表结点*/
    {
        
    	int in;                 /*顶点入度*/
    	int data;               /*顶点域，存储顶点信息*/
    	EdgeNode* firstedge;     /*边表头指针*/
    } VertexNode,AdjList[MAXVEX];
    
    typedef struct
    {
        
    	AdjList adjList;
    	int numVertexes, numEdges;    /*图中当前顶点数和边数*/
    }graphAdjList,*GraphAdjList;

在管法由．我还需要辅助的数据结构–栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。

现在我们来看代码,并且模拟运行它。

/*拓扑排序，若GL无回路，则输出拓扑排序序列并返回true，若有回路返回false*/
    bool TopologicalSort(GraphAdjList GL)
    {
        
    	EdgeNode* e;
    	int i, k, gettop;
    	int top = 0;        /*用于栈指针下标*/
    	int count = 0;      /*用于统计输出顶点的个数*/
    	int* stack;         /*建栈存储入度为0的顶点*/
    	stack = (int*)malloc(GL->numVertexes * sizeof(int));
    
    	for (i=0;i<GL->numVertexes;i++)
    	{
        
    		if (GL->adjList[i].in==0)
    		{
        
    			stack[++top] = i;   /*将入度为0的顶点入栈*/
    		}
    	}
    
    	while (top!=0)
    	{
        
    		gettop = stack[top--];/*出栈*/
    		printf("%d ->",GL->adjList[gettop].data);/*打印此顶点*/
    		count++;/*统计输出顶点数*/
    		for (e=GL->adjList[gettop].firstedge;e;e=e->next)
    		{
        
    			/*对此顶点弧表遍历*/
    			k = e->adjvex;
    			if (!(--GL->adjList[k].in))/*将k号顶点邻接点的入度减1*/
    			{
        
    				stack[++top] = k;/*若为0则入栈，以便于下次循环输出*/
    			}
    		}
    	}
    
    	if (count<GL->numVertexes)/*如果count小于顶点数，说明存在环*/
    	{
        
    		return false;
    	}
    	else
    	{
        
    		return true;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]

1．程序开始运行，第3~7行都是变量的定义，其中stack是一个栈，用来存储整型的数字。  
2．第8~10行，作了一个循环判断，把入度为0的顶点下标都入栈，从图7-8-3的右图邻接表可知，此时 stack应该为:\{0，1，3\}，即v0、v1、v3的顶点入度为0，如图7-8-3所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]  
3．第12~23行，while循环，当栈中有数据元素时，始终循环。  
4．第14~～16行，v3出栈得到gettop=3。并打印此顶点，然后count 加1。  
5．第17~22行，循环其实是对v3顶点对应的弧链表进行遍历，即图7-8-4中的灰色部分，找到v3连接的两个顶点v2和 v13，并将它们的入度减少一位，此时v2和v3的in值都为1。它的目的是为了将v3顶点上的弧删除。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 4]  
6．再次循环，第12~23行。此时处理的是顶点v1。经过出栈、打印、count=2  
后，我们对v1到v2、V4、v8的弧进行了遍历。并同样减少了它们的入度数，此时v2入度为0，于是由第20~21行知，v2入栈，如图7-8-5所示。试想，如果没有在顶点表中加入 in这个入度数据域，20行的判断就必须要是循环，这显然是要消耗时间的,我们利用空间换取了时间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 5]  
7．接下来，就是同样的处理方式了。图7-8-6展示了V2 V6 V0 V4 V5 V8的打印删除过程，后面还剩几个顶点都类似,就不图示了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 7]

8．最终拓扑排序打印结果为3->1->2->6->0->4->5->8->7->12->9->10->13->11。  
当然这结果并不是唯一的一种拓扑排序方案。

分析整个算法，对一个具有n个顶点e条弧的AOV网来说，第8~10行扫描顶点表，将入度为0的顶点入栈的时间复杂为o(n)，而之后的while 循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，所以整个算法的时间复杂度为o(n+e)。

[20210222164340611.png]: /images/20221024/2f288c03158a4c8cb900fc068b326f80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221024/9eddc51f40b2465cafaaecddf8eec343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: /images/20221024/684c808bde8a4defb60f710dc8e6899c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]: /images/20221024/9264e23202f44cc689b3c7c707394794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]: /images/20221024/35d9d5046f9e46be9fc84d2fcc7ee373.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 4]: /images/20221024/3f66b9cf985c458e82461d0bef8d4b9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 5]: /images/20221024/956c0c2f22aa4dd48315dc5c74ab047c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 6]: /images/20221024/954820ab45a84b5fb5ff7b52d62e2ee1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 7]: /images/20221024/ebafc87389b64bb4b08abd32fc6e9402.png