经典算法之拓扑排序

迈不过友情╰ 2022-05-20 09:41 216阅读 0赞

# 定义： #

把AOV网（用定点表示活动，用弧表示活动间优先关系的有向图）络中各个顶点按照它们互相之间的优先关系排列成一个线性序列的过程叫做拓扑排序。

# 方法： #

1.  在有向图中选一个没有前驱的顶点并且输出
2.  从图中删除该顶点和所有以它为尾的弧，即删除所有与它有关的边。
3.  重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

# 例题： #

![70][]

首先我们找到无前驱顶点C1和C9，我们删除掉C1，输出C1，并删除所有与C1相连的边

![70 1][]

接着再从C2，C4，C9这三个无前驱顶点中选择一个删除掉，我们删除C2，输出C2，并删除所有与C2相连的边

![70 2][]![70 3][]

### 重复操作 ###

![70 4][]![70 5][]

![70 6][]

![70 7][]

![70 8][]

最终得拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8。

注意：拓扑序列并不唯一，C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 也是一种拓扑序列。

# 代码实现： #

#include <iostream>
    
    using namespace std;
    #define N 13
    int main()
    {
        int map[N][N]; //邻接矩阵
        // 初始化矩阵的值全部为0表示各个顶点间没有边连接
        for(int i = 0; i <= N-1; i++){
            for(int j = 0; j <= N-1; j++){
                map[i][j] = 0;
            }
        }
    
        int a,b;  //定义两个变量，用来输入
        int v,l;  //顶点数和边数
    
        cout << "请输入顶点数：";
        cin >> v;
        cout << "请输入边数：";
        cin >> l;
        cout << "请输入边：" << endl;
    
        for(int i = 1; i <= l; i++){
                cin >> a >> b;
                map[a][b] = 1; // 表示顶点a指向顶点b的边
        }
        cout << "邻接矩阵如下所示\n" << endl;
        for(int i = 1; i <= N-1; i++){
            for(int j = 1; j <= N-1; j++){
                cout << map[i][j];
            }
            cout << endl;
        }
    
        int k; //用于计算度数
        int ID[N]; //用于存放入度
        for(int i = 1; i <= v; i++){  // 计算入度
            k = 0;
            for(int j = 1; j <= v; j++){
                if(map[j][i] == 1) //如果顶点j到顶点i有边，则顶点i的入度+1
                    k++;
            }
            ID[i] = k;
        }
        //1、在有向图中选一个没有前驱的顶点并且输出
        cout << "\n\n拓扑序列： ";
        int count = 0;   //最后用来判断是否所有的顶点输出
        while(1){
            for(int i = 1; i <= v; i++){
                if(ID[i] == 0){
                    cout << i << " ";  //输出顶点
                    count++;
                    //2、从图中删除该顶点和所有以它为尾的弧，即删除所有与它有关的边。
                    ID[i] = -1; //将此顶点入度设为-1，表示删除
                    for(int j = 1; j <= v; j++){
                        if(map[i][j] == 1){     //如果顶点j与顶点i有边，则删除这条边，并且顶点j的入度-1
                            ID[j]--;
                        }
                    }
                }
            }
            //3、重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。
            if(count == v){
                break;  //若count == 顶点数，表示所有顶点的入度都为-1，即所有的边均已输出，停止操作。
            }
        }
        return 0;
    }

# 输入： #

12    16
    
    1   2 
    1   4
    1   3
    1   12
    2   3
    3   5
    3   7
    3   8
    4   5
    5   7
    9   12
    9   10
    9   11
    10  12
    11  6
    6   8

# 输出： #

拓扑序列：1 2 3 4 5 7 9 10 11 12 6 8

![70 9][]

[70]: /images/20220520/30c7afa91e904c1296b12081937e9861.png
[70 1]: /images/20220520/5bffa822eabc4da6a6f58a72ba727d9c.png
[70 2]: https://img-blog.csdn.net/20180716200324324?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NjE4Nzk3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: /images/20220520/a4558311473d47209874945550b67ed6.png
[70 4]: https://img-blog.csdn.net/20180716200635441?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NjE4Nzk3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 5]: /images/20220520/b65139a483bf4ed19ca73d2ec162ee86.png
[70 6]: /images/20220520/93236c4adda24478bb04af809d5a7a2c.png
[70 7]: /images/20220520/d0404ad4abd249bfa7c3dda42df78a7f.png
[70 8]: /images/20220520/4a7f7f9a31634a66b122e81612c43319.png
[70 9]: /images/20220520/56f658f1bd934b42800a449b019a864f.png