数据结构---拓扑排序详解

朴灿烈づ我的快乐病毒、 2022-09-26 15:50 173阅读 0赞

*前言*  
The time of test,family is best.  
Name:Willam  
Time:2017/3/6

## 1、拓扑排序的介绍 ##

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。  
拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。  
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

## 2、拓扑排序的实现步骤 ##

1.  在有向图中选一个没有前驱的顶点并且输出
2.  从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）
3.  重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。

## 3、拓扑排序示例手动实现 ##

如果我们有如下的一个有向无环图，我们需要对这个图的顶点进行拓扑排序，过程如下：  
![这里写图片描述][SouthEast]

首先，我们发现V6和v1是没有前驱的，所以我们就随机选去一个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：  
![这里写图片描述][SouthEast 1]

然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：  
![这里写图片描述][SouthEast 2]

然后，我们又发现V4和V3都是没有前驱的，那么我们就随机选取一个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果：  
![这里写图片描述][SouthEast 3]

然后，我们输出没有前驱的顶点V3，得到如下结果：  
![这里写图片描述][SouthEast 4]

然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的一个拓扑序列为：

v6–>v1—->v4—>v3—>v5—>v2

## 4、拓扑排序的代码实现 ##

下面，我们将用两种方法来实现我么的拓扑排序：

1.  Kahn算法
2.  基于DFS的拓扑排序算法

首先我们先介绍第一个算法的思路：  
Kahn的算法的思路其实就是我们之前那个手动展示的拓扑排序的实现，我们先使用一个栈保存入度为0 的顶点，然后输出栈顶元素并且将和栈顶元素有关的边删除，减少和栈顶元素有关的顶点的入度数量并且把入度减少到0的顶点也入栈。具体的代码如下：

bool Graph_DG::topological_sort() {
        cout << "图的拓扑序列为：" << endl;
        //栈s用于保存栈为空的顶点下标
        stack<int> s;
        int i;
        ArcNode * temp;
        //计算每个顶点的入度，保存在indgree数组中
        for (i = 0; i != this->vexnum; i++) {
            temp = this->arc[i].firstarc;
            while (temp) {
                ++this->indegree[temp->adjvex];
                temp = temp->next;
            }
    
        }
    
        //把入度为0的顶点入栈
        for (i = 0; i != this->vexnum; i++) {
            if (!indegree[i]) {
                s.push(i); 
            }
        }
        //count用于计算输出的顶点个数
        int count=0;
        while (!s.empty()) {
       //如果栈为空，则结束循环
            i = s.top();
            s.pop();//保存栈顶元素，并且栈顶元素出栈
            cout << this->arc[i].data<<" ";//输出拓扑序列
            temp = this->arc[i].firstarc;
            while (temp) {
                if (!(--this->indegree[temp->adjvex])) {
       //如果入度减少到为0，则入栈
                    s.push(temp->adjvex);
                }
                temp = temp->next;
            }
            ++count;
        }
        if (count == this->vexnum) {
            cout << endl;
            return true;
        } 
        cout << "此图有环，无拓扑序列" << endl;
        return false;//说明这个图有环
    }

现在，我们来介绍第二个算法的思路：  
其实DFS就是深度优先搜索，它每次都沿着一条路径一直往下搜索，知道某个顶点没有了出度时，就停止递归，往回走，所以我们就用DFS的这个思路，我们可以得到一个有向无环图的拓扑序列，其实DFS很像Kahn算法的逆过程。具体的代码实现如下：

bool Graph_DG::topological_sort_by_dfs() {
        stack<string> result;
        int i;
        bool * visit = new bool[this->vexnum];
        //初始化我们的visit数组
        memset(visit, 0, this->vexnum);
        cout << "基于DFS的拓扑排序为：" << endl;
        //开始执行DFS算法
        for (i = 0; i < this->vexnum; i++) {
            if (!visit[i]) {
                dfs(i, visit, result);
            }
        }
        //输出拓扑序列，因为我们每次都是找到了出度为0的顶点加入栈中，
        //所以输出时其实就要逆序输出，这样就是每次都是输出入度为0的顶点
        for (i = 0; i < this->vexnum; i++) {
            cout << result.top() << " ";
            result.pop();
        }
        cout << endl;
        return true;
    }
    void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
    
            visit[n] = true;
            ArcNode * temp = this->arc[n].firstarc;
            while (temp) {
                if (!visit[temp->adjvex]) {
                    dfs(temp->adjvex, visit,result);
                }
                temp = temp->next;
            }
            //由于加入顶点到集合中的时机是在dfs方法即将退出之时，
            //而dfs方法本身是个递归方法，
            //仅仅要当前顶点还存在边指向其他不论什么顶点，
            //它就会递归调用dfs方法，而不会退出。
            //因此，退出dfs方法，意味着当前顶点没有指向其他顶点的边了
            //，即当前顶点是一条路径上的最后一个顶点。
            //换句话说其实就是此时该顶点出度为0了
            result.push(this->arc[n].data);
    
    }

两种算法总结：  
对于基于DFS的算法，增加结果集的条件是：顶点的出度为0。这个条件和Kahn算法中入度为0的顶点集合似乎有着异曲同工之妙，Kahn算法不须要检测图是否为DAG，假设图为DAG，那么在入度为0的栈为空之后，图中还存在没有被移除的边，这就说明了图中存在环路。而基于DFS的算法须要首先确定图为DAG，当然也可以做出适当调整，让环路的检测測和拓扑排序同一时候进行，毕竟环路检測也可以在DFS的基础上进行。  
二者的复杂度均为O(V+E)。

## 5、完整的代码和输出展示 ##

*  topological\_sort.h文件的代码

/************************************************************/
    /*                程序作者：Willam                          */
    /*                程序完成时间：2017/3/6                    */
    /*                有任何问题请联系：2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #pragma once
    //#pragma once是一个比较常用的C/C++杂注，
    //只要在头文件的最开始加入这条杂注，
    //就能够保证头文件只被编译一次。
    
    /*
    拓扑排序必须是对有向图的操作
    算法实现：
    （1）Kahn算法
    （2）DFS算法
    采用邻接表存储图
    */
    #include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    //表结点
    struct ArcNode {
        ArcNode * next; //下一个关联的边
        int adjvex;   //保存弧尾顶点在顶点表中的下标
    };
    struct Vnode {
        string data; //顶点名称
        ArcNode * firstarc; //第一个依附在该顶点边
    };
    
    class Graph_DG {
    private:
        int vexnum; //图的顶点数
        int edge;   //图的边数
        int * indegree; //每条边的入度情况
        Vnode * arc; //邻接表
    public:
        Graph_DG(int, int);
        ~Graph_DG();
        //检查输入边的顶点是否合法
        bool check_edge_value(int,int);
        //创建一个图
        void createGraph();
        //打印邻接表
        void print();
        //进行拓扑排序,Kahn算法
        bool topological_sort();
        //进行拓扑排序，DFS算法
        bool topological_sort_by_dfs();
        void dfs(int n,bool * & visit, stack<string> & result);
    };

*  topological\_sort.cpp文件代码

#include"topological_sort.h"
    
    Graph_DG::Graph_DG(int vexnum, int edge) {
        this->vexnum = vexnum;
        this->edge = edge;
        this->arc = new Vnode[this->vexnum];
        this->indegree = new int[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) {
            this->indegree[i] = 0;
            this->arc[i].firstarc = NULL;
            this->arc[i].data = "v" + to_string(i + 1);
        }
    }
    //释放内存空间
    Graph_DG::~Graph_DG() {
        ArcNode * p, *q;
        for (int i = 0; i < this->vexnum; i++) {
            if (this->arc[i].firstarc) {
                p = this->arc[i].firstarc;
                while (p) {
                    q = p->next;
                    delete p;
                    p = q;
                }
            }
        }
        delete [] this->arc;
        delete [] this->indegree;
    }
    //判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end) {
        if (start<1 || end<1 || start>vexnum || end>vexnum) {
            return false;
        }
        return true;
    }
    void Graph_DG::createGraph() {
        int count = 0;
        int start, end;
        cout << "输入每条起点和终点的顶点编号（从1开始编号）" << endl;
        while (count != this->edge) {
            cin >> start;
            cin >> end;
            //检查边是否合法
            while (!this->check_edge_value(start, end)) {
                cout << "输入的顶点不合法，请重新输入" << endl;
                cin >> start;
                cin >> end;
            }
            //声明一个新的表结点
            ArcNode * temp = new ArcNode;
            temp->adjvex = end - 1;
            temp->next = NULL;
            //如果当前顶点的还没有边依附时，
            if (this->arc[start - 1].firstarc == NULL) {
                this->arc[start - 1].firstarc = temp;
            }
            else {
                ArcNode * now = this->arc[start - 1].firstarc;
                while(now->next) {
                    now = now->next;
                }//找到该链表的最后一个结点
                now->next = temp;
            }
            ++count;
        }
    }
    void Graph_DG::print() {
        int count = 0;
        cout << "图的邻接矩阵为：" << endl;
        //遍历链表，输出链表的内容
        while (count != this->vexnum) {
            //输出链表的结点
            cout << this->arc[count].data<<" ";
            ArcNode * temp = this->arc[count].firstarc;
            while (temp) {
                cout<<"<"<< this->arc[count].data<<","<< this->arc[temp->adjvex].data<<"> ";
                temp = temp->next;
            }
            cout << "^" << endl;
            ++count;
        }
    }
    
    bool Graph_DG::topological_sort() {
        cout << "图的拓扑序列为：" << endl;
        //栈s用于保存栈为空的顶点下标
        stack<int> s;
        int i;
        ArcNode * temp;
        //计算每个顶点的入度，保存在indgree数组中
        for (i = 0; i != this->vexnum; i++) {
            temp = this->arc[i].firstarc;
            while (temp) {
                ++this->indegree[temp->adjvex];
                temp = temp->next;
            }
    
        }
    
        //把入度为0的顶点入栈
        for (i = 0; i != this->vexnum; i++) {
            if (!indegree[i]) {
                s.push(i); 
            }
        }
        //count用于计算输出的顶点个数
        int count=0;
        while (!s.empty()) {
       //如果栈为空，则结束循环
            i = s.top();
            s.pop();//保存栈顶元素，并且栈顶元素出栈
            cout << this->arc[i].data<<" ";//输出拓扑序列
            temp = this->arc[i].firstarc;
            while (temp) {
                if (!(--this->indegree[temp->adjvex])) {
       //如果入度减少到为0，则入栈
                    s.push(temp->adjvex);
                }
                temp = temp->next;
            }
            ++count;
        }
        if (count == this->vexnum) {
            cout << endl;
            return true;
        } 
        cout << "此图有环，无拓扑序列" << endl;
        return false;//说明这个图有环
    }
    bool Graph_DG::topological_sort_by_dfs() {
        stack<string> result;
        int i;
        bool * visit = new bool[this->vexnum];
        //初始化我们的visit数组
        memset(visit, 0, this->vexnum);
        cout << "基于DFS的拓扑排序为：" << endl;
        //开始执行DFS算法
        for (i = 0; i < this->vexnum; i++) {
            if (!visit[i]) {
                dfs(i, visit, result);
            }
        }
        //输出拓扑序列，因为我们每次都是找到了出度为0的顶点加入栈中，
        //所以输出时其实就要逆序输出，这样就是每次都是输出入度为0的顶点
        for (i = 0; i < this->vexnum; i++) {
            cout << result.top() << " ";
            result.pop();
        }
        cout << endl;
        return true;
    }
    void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
    
            visit[n] = true;
            ArcNode * temp = this->arc[n].firstarc;
            while (temp) {
                if (!visit[temp->adjvex]) {
                    dfs(temp->adjvex, visit,result);
                }
                temp = temp->next;
            }
            //由于加入顶点到集合中的时机是在dfs方法即将退出之时，
            //而dfs方法本身是个递归方法，
            //仅仅要当前顶点还存在边指向其他不论什么顶点，
            //它就会递归调用dfs方法，而不会退出。
            //因此，退出dfs方法，意味着当前顶点没有指向其他顶点的边了
            //，即当前顶点是一条路径上的最后一个顶点。
            //换句话说其实就是此时该顶点出度为0了
            result.push(this->arc[n].data);
    
    }

*  main.cpp文件：

#include"topological_sort.h"
    
    //检验输入边数和顶点数的值是否有效，可以自己推算为啥：
    //顶点数和边数的关系是：((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
    
        cout << "输入图的顶点个数和边的条数：" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法，请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.topological_sort();
        graph.topological_sort_by_dfs();
        system("pause");
        return 0;
    
    }

*  输入：

6 8
    1 2
    1 3
    1 4
    3 2
    3 5
    4 5
    6 4
    6 5

输出：  
![这里写图片描述][SouthEast 5]

输入：

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

输出：  
![这里写图片描述][SouthEast 6]

[SouthEast]: /images/20220708/9e30324b43b14eef8b37c717773231fc.png
[SouthEast 1]: /images/20220708/178e998cb6c94bac89986becd22478b6.png
[SouthEast 2]: /images/20220708/01bc8651c1c847ab9b1b2c57a7c4d55f.png
[SouthEast 3]: /images/20220708/96183e40a4554663955afe9d28c88c8f.png
[SouthEast 4]: /images/20220708/5d38b3371e504cafb6d20f1392100b25.png
[SouthEast 5]: /images/20220708/f76d9f9777a748a4a643f88a8f52d92a.png
[SouthEast 6]: /images/20220708/74379f8ab0404a43bb77874ab462670e.png