数据结构（20）图的拓扑排序

喜欢ヅ旅行 2023-03-04 15:27 6阅读 0赞

### 数据结构（20）图的拓扑排序 ###

*   *   *  前言
         *  拓扑排序算法的实现
         *  全部代码

### 前言 ###

拓扑排序是有向无环图中的应用。所谓有向无环图，顾名思义，首先要求图是有向图，其次要求图中不能有回路，即无环。

使用有向无环图，可以来表示一个流程图，图中的每一条有向边用来表示子工程之间的次序（领先）关系。有时候，我们会关心工程的进行问题，假设子工程A领先于子工程B，这意味着要完成子工程B必须先完成子工程A，因此A必须在B之前进行，否则整个工程就无法顺利进行。

那么，如何得到整个工程的进行顺序呢？对有向无环图进行拓扑排序，将其转化为拓扑序列，就能解决这个问题。

### 拓扑排序算法的实现 ###

要进行拓扑排序，思路很简单：

1.  首先，在图中寻找一个入度为零（没有前驱）的顶点，将其输出。
    
    没有前驱意味着要完成这项子工程不需要先完成其他子工程，因此可以先完成此工程。
2.  从图中删除掉这个顶点和所有以它为尾的弧
    
    删除掉这个顶点，意味着该项工程已经完成了，那么以它为前提的工程也就可以开始进行了。
3.  重复1-2步，直到图中的全部顶点都输出完毕；或者当前的图中，已经不存在没有前驱的顶点了。假如是后一种情况，说明图中存在环。  
    ![img\_1][img_1]  
    ![img\_2][img_2]
4.  如图所示，首先寻找到入度为0的顶点F，输出F，并且删除掉以它为尾的弧F-D、F-E，修改D、E的入度
5.  寻找到入度为0的顶点A，输出A，并且删除掉以它为尾的弧A-B、A-C、A-D，修改B、C、D的入度
6.  寻找到入度为0的顶点C，输出C，并且删除掉以它为尾的弧C-B、C-E，修改B、E的入度

![img\_3][img_3]

1.  寻找到入度为0的顶点B，输出B，无以它为尾的弧
2.  寻找到入度为0的顶点D，输出D，并且删除掉以它为尾的弧D-E，修改E的入度
3.  寻找到入度为0的顶点E，输出E，无以它为尾的弧

可以发现，入度为0的顶点不一定唯一，从中随机选择即可；这意味着拓扑排序的结果不一定是唯一的。

这个算法该怎么实现呢？

首先很显然，我们需要维护一个count数组，用于记录每个顶点当前的入度。当某个顶点入度为零时，意味着可以将其输出了。

从图中删除掉这个顶点，可以考虑用一个特殊值（-1）标记该顶点的访问情况，当count\[i\] == -1时，说明该顶点已经访问过了。而删除掉以它为尾的弧，意味着少了一条边到达本顶点的邻接顶点，也就是说将邻接顶点的入度减一即可。

如果这样设计，我们需要不断遍历count数组，寻找到count\[i\] == 0的顶点，并且在合适的时候（count数组内所有的值都等于-1时）退出这个循环，可以是可以，总归有些麻烦。

不如转换一下思路，使用栈（或者队列）的结构：首先计算所有顶点的初始入度，然后将count初值为零的顶点全部入栈，再将栈中的顶点依次出栈（出栈的同时修改其所有邻接顶点的入度，若为零则邻接顶点也入栈）。由于有n个顶点，因此出栈的操作应该循环n次；若在少于n次时栈已经空了，说明图中存在回路。

//拓扑排序
    void TopologicalSort2(GraphLnk *g){ 
        int n = g->NumVertices;
        
        //创建辅助数组
        int *count = (int *)malloc(sizeof(int)*n);
        assert(count != NULL);
        //初始化辅助数组
        for (int i = 0; i < n; i ++) { 
            count[i] = 0;
        }
        
        //统计每个顶点的初始入度
        Edge *p;
        for (int i = 0; i < n; i ++) { 
            p = g->NodeTable[i].adj;
            while (p != NULL) { 
                //遍历本顶点的边列表，获取到边的另一个顶点的下标
                //则另一个顶点的入度加一
                count[p->dest] ++;
                p = p->Link;
            }
        }
        
        //初始化栈
        SeqStack stack;
        InitStack(&stack);
        for (int i = 0;  i < n; i ++) { 
            //将初始时每个入度为0的顶点都入栈
            if (count[i] == 0) { 
                //入栈
                Push(&stack, i);
            }
        }
        
        int v,w;
        //每个顶点依次出栈
        for (int i = 0; i < n; i ++) { 
            if (IsEmpty(&stack)) { 
                //在小于n时栈就空了，说明有回路
                printf("网络中有回路\n");
                return;
            }else{ 
                //获取栈顶元素
                GetTop(stack, &v);
                //栈顶元素出栈
                Pop(&stack);
                //访问本顶点
                printf("%2c",g->NodeTable[v].data);
                
                //删除所有以本顶点为结尾的弧->本顶点的所有邻接顶点入度减一
                //获取第一个邻接顶点
                w = GetFirstNeighbor(g, g->NodeTable[v].data);
                while(w != -1) { 
                    if (--count[w] == 0) { 
                        //邻接顶点减一后入度为零，入栈
                        Push(&stack, w);
                    }
                    //获取下一个邻接顶点
                    w = GetNextNeighbor(g, g->NodeTable[v].data, g->NodeTable[w].data);
                }
            }
        }
        
        free(count);
    }

如果不想使用先前写好的栈结构的话，可以外设一个top指针来达到栈的结果，此时count数组有两个功能：若顶点还未需要访问，则count数组中保存的是当前顶点的入度；若顶点的入度为0，则count数组中保存的是下一个要访问的顶点的下标地址。

![img\_4][img_4]

如图所示，当初始化完count数组时，有A、F两个需要访问的顶点。那么入栈操作即使count\[i\] = top，top = i。此时top保存的是当前栈顶元素的下标地址，而count数组中A、F的位置不再保存其入度，而是保存栈中下一个元素的位置。例如此时F中存放着A的下标地址，A中存放-1，说明A没有下一个元素，栈空了。

出栈操作即top = count\[top\]，例如此时需要将F出栈，则让top指针指向A顶点即可。

//拓扑排序
    void TopologicalSort(GraphLnk *g){ 
        int n = g->NumVertices;
        
        //创建辅助数组
        int *count = (int *)malloc(sizeof(int)*n);
        assert(count != NULL);
        //初始化辅助数组
        for (int i = 0; i < n; i ++) { 
            count[i] = 0;
        }
        
        //统计每个顶点的初始入度
        Edge *p;
        for (int i = 0; i < n; i ++) { 
            p = g->NodeTable[i].adj;
            while (p != NULL) { 
                count[p->dest] ++;
                p = p->Link;
            }
        }
        
        int top = -1;
        for (int i = 0;  i < n; i ++) { 
            //找到入度为0的顶点
            if (count[i] == 0) { 
                //入栈
                count[i] = top;
                top = i;
            }
        }
        
        int v,w;
        for (int i = 0; i < n; i ++) { 
            if (top == -1) { 
                printf("网络中有回路\n");
                return;
            }else{ 
                //获取栈顶元素
                v = top;
               //出栈
                top = count[top];
                printf("%2c",g->NodeTable[v].data);
                
                w = GetFirstNeighbor(g, g->NodeTable[v].data);
                while(w != -1) { 
                    if (--count[w] == 0) { 
                        //邻接顶点入度为零-入栈
                        count[w] = top;
                        top = w;
                    }
                    w = GetNextNeighbor(g, g->NodeTable[v].data, g->NodeTable[w].data);
                }
            }
        }
        
        free(count);
    }

这样虽然也能实现目标，但是一个数组拥有两种含义，容易产生混乱，因此还是直接使用栈更容易理解一些。

### 全部代码 ###

因为使用了之前写好的队列和栈结构，就不一一复制了，传文件。

[拓扑排序-微云][-]

[img_1]: /images/20230208/e84b50d55952499ea25d26d5827de5e4.png
[img_2]: /images/20230208/5bba3db7133043498a77d3c37320ddd2.png
[img_3]: /images/20230208/e9747c20661744f4a591f5bd61b01e75.png
[img_4]: /images/20230208/b9a881f52bdf47288d0bf9a772a725de.png
[-]: https://share.weiyun.com/5zL671Xb