c/c++开发分享详解C++实现拓扑排序算法

一、拓扑排序的介绍拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用


一、拓扑排序的介绍

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

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

二、拓扑排序的实现步骤

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

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

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

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

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

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

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

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

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

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

然后,我们又发现v4和v3都是没有前驱的,那么我们就随机选取一个顶点输出(具体看你实现的算法和图存储结构),我们输出v4,得到如下图结果:

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

然后,我们输出没有前驱的顶点v3,得到如下结果:

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

然后,我们分别输出v5和v2,最后全部顶点输出完成,该图的一个拓扑序列为:

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

四、拓扑排序的代码实现

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

1.kahn算法

2.基于dfs的拓扑排序算法

首先我们先介绍第一个算法的思路:

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

%ignore_pre_1%

现在,我们来介绍第二个算法的思路:
其实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++杂注,  //只要在头文件的最开始加入这条杂注,  //就能够保证头文件只被编译一次。    /*  拓扑排序必须是对有向图的操作  算法实现:  (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

输出:

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

输入:

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++实现拓扑排序算法的详细内容,更多关于c++ 拓扑排序算法的资料请关注<猴子技术宅>其它相关文章!

需要了解更多c/c++开发分享详解C++实现拓扑排序算法,都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/637210.html

发表评论

邮箱地址不会被公开。 必填项已用*标注