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

3/8/2017来源:ASP.NET技巧人气:649

前言 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、拓扑排序的实现步骤

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

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

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

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

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

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

然后,我们输出没有前驱的顶点V3,得到如下结果: 这里写图片描述

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

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

4、拓扑排序的代码实现

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

Kahn算法 基于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

输出: 这里写图片描述

输入:

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

输出: 这里写图片描述