120

分享到

详解C++实现拓扑排序算法

2024-04-02 19:04:59 120人浏览安东尼

摘要

目录一、拓扑排序的介绍二、拓扑排序的实现步骤三、拓扑排序示例手动实现四、拓扑排序的代码实现五、完整的代码和输出展示一、拓扑排序的介绍拓扑排序对应施工的流程图具有特别重要的作用，它可

一、拓扑排序的介绍

拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

二、拓扑排序的实现步骤

1.在有向图中选一个没有前驱的顶点并且输出

2.从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）

3.重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。

三、拓扑排序示例手动实现

如果我们有如下的一个有向无环图，我们需要对这个图的顶点进行拓扑排序，过程如下：

这里写图片描述

首先，我们发现V6和v1是没有前驱的，所以我们就随机选去一个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：

这里写图片描述

然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：

这里写图片描述

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

这里写图片描述

然后，我们输出没有前驱的顶点V3，得到如下结果：

这里写图片描述

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

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

四、拓扑排序的代码实现

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

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)。

五、完整的代码和输出展示

topological_sort.h文件的代码


#pragma once
//#pragma once是一个比较常用的C/C++杂注，
//只要在头文件的最开始加入这条杂注，
//就能够保证头文件只被编译一次。


#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

输出：

这里写图片描述

输入：

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

输出：

这里写图片描述

以上就是详解c++实现拓扑排序算法的详细内容，更多关于C++ 拓扑排序算法的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 详解C++实现拓扑排序算法

本文链接: https://www.lsjlt.com/news/128114.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

详解C++实现拓扑排序算法

目录一、拓扑排序的介绍二、拓扑排序的实现步骤三、拓扑排序示例手动实现四、拓扑排序的代码实现五、完整的代码和输出展示一、拓扑排序的介绍拓扑排序对应施工的流程图具有特别重要的作用，它可...

99+

2024-04-02
详解Java实现拓扑排序算法

目录一、介绍二、拓扑排序算法分析三、拓扑排序代码实现一、介绍百科上这么定义的：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中...

99+

2024-04-02
C/C++浅析邻接表拓扑排序算法的实现

目录前言一、拓扑排序算法的思路二、实现步骤1.求个顶点的入度2.拓扑排序的实现三、测试结果总结前言在软件开发、施工过程、教学安排等等的一系列活动中，往往需要一个有向无环图来表示其是...

99+

2024-04-02
C++详细讲解图的拓扑排序

目录一、前言二、算法流程三、有向图的拓扑排序一、前言且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点 x到顶点 y的路径，那么在序列中顶点 x 出现在顶点...

99+

2024-04-02
Java实现拓扑排序算法的示例代码

目录拓扑排序原理1.点睛2.拓扑排序3.算法步骤4.图解拓扑排序算法实现1.拓扑图2.实现代码3.测试拓扑排序原理 1.点睛一个无环的有向图被称为有向无环图。有向无环图是描述一个工...

99+

2024-04-02
Java如何实现拓扑排序

今天小编给大家分享一下Java如何实现拓扑排序的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。铺垫有向图：我们这节要讲的算法涉...

99+

2023-06-30
拓扑排序Python实现的过程

目录有向无环图拓扑排序算法步骤代码实现总结有向无环图拓扑排序是针对有向无环图（DAG, Directed Acyclic Graph）的具有以下性质：如果这个图不是 DAG，那...

99+

2023-01-31

拓扑排序Python 拓扑排序 Python拓扑排序
C++图的拓扑排序是什么

本文小编为大家详细介绍“C++图的拓扑排序是什么”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++图的拓扑排序是什么”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。一、前言且该序列必须满足下面两个条件：每个顶点...

99+

2023-06-30
Java实现拓扑排序的示例代码

目录铺垫简介工作过程数据结构拓扑排序测试样例1测试样例2总结铺垫有向图：我们这节要讲的算法涉及到有向图，所以我先把有向图的一些概念说一下，文章后面就不做解释啦。首先有向图节点与节点...

99+

2024-04-02
详解C++实现链表的排序算法

目录一、链表排序二、另外一种链表排序方式三、比较两种排序的效率四、下面通过交换结点实现链表的排序一、链表排序最简单、直接的方式（直接采用冒泡或者选择排序，而且不是交换结点，只交换数...

99+

2024-04-02
Java数据结构之有向图的拓扑排序详解

目录前言拓扑排序介绍检测有向图中的环实现思路API设计代码实现基于深度优先的顶点排序实现思路API设计代码实现拓扑排序API设计代码实现测试验证前言在现实生活中，我们经常会同一时间...

99+

2022-11-13

Java有向图拓扑排序 Java 有向图 Java 拓扑排序
超详细解析C++实现归并排序算法

目录一、前言分治算法分治算法解题方法二、归并排序1.问题分析2.算法设计3.算法分析三、AC代码一、前言分治算法归并排序，其实就是一种分治算法，那么在了解归并排序之前，我们先来...

99+

2024-04-02
C++归并排序算法详解

目录一.算法简介二.实现过程总结一.算法简介归并排序算法的平均时间复杂度是O(nlo...

99+

2024-04-02
Java 归并排序算法、堆排序算法实例详解

基本思想：　　归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序示例：合并方法：设r[i…n]由两个有序子表r[i…m...

99+

2023-05-31

java 归并排序堆排序
C#实现快速排序算法

快速排序是应用最广泛的排序算法，流行的原因是它实现简单，适用于各种不同情况的输入数据且在一般情况下比其他排序都快得多。快速排序是原地排序（只需要一个很小的辅助栈），将长度为 N 的...

99+

2024-04-02
超详细解析C++实现快速排序算法的方法

目录一、前言1.分治算法2.分治算法解题方法二、快速排序1.问题分析2.算法设计3.算法分析三、AC代码一、前言 1.分治算法快速排序，其实是一种分治算法，那么在了解快速排序之前，...

99+

2024-04-02
C语言实现冒泡排序算法的示例详解

目录1. 问题描述2. 问题分析3. 算法设计动图演示4. 程序设计设计一设计二结论5. 流程框架6. 代码实现7. 问题拓展1. 问题描述对N个整数（数据由键盘输入）进行升序排列...

99+

2024-04-02
c++实现排序算法之希尔排序方式

目录排序算法之希尔排序基本思想希尔排序算法复杂度分析关于希尔排序的问题分析排序算法之希尔排序及时间复杂度分析希尔排序时间复杂度排序算法之希尔排序基本思想将相距某个“增...

99+

2024-04-02
TypeScript十大排序算法插入排序实现示例详解

目录一. 插入排序的定义二. 插入排序的流程三. 插入排序的图解四. 插入排序的代码五. 插入排序的时间复杂度六. 插入排序的总结一. 插入排序的定义插入排序就像是你打扑克牌，你...

99+

2023-02-23

TypeScript插入排序算法 TypeScript 算法
C#实现冒泡排序和插入排序算法

1.选择排序（冒泡排序）升序用第一个元素跟其他元素比较，如果该元素比其他元素，则交换，保证该元素是最小的。然后再用第二个元素跟后面其他的比较，保证第二个元素是除第一个最小的。依次...

99+

2024-04-02