拓扑排序
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
适用条件
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图(DAG)才能有拓扑排序,非DAG没有拓扑排序。
这里的条件通俗一点讲,就是假设每个节点都是一个事件,事件与事件之间存在先后关系,比如吃饭之前需要做饭,但如果这些事件里面有个环,便不能构成先后顺序了,所以拓扑排序只适用于DAG
实现思路
- 在有向图中选一个没有前驱的顶点并且输出
- 从图中删除该顶点和所有以它为尾的弧(白话就是:删除所有和它有关的边)
- 重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱的顶点为止,后者代表我们的有向图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。
假设我们有这样一个DAG
我们得选择一个没有前驱的节点,这里有1和6,我们先选择1。这里我们输出1,并且删除跟1有关的边
这里我们发现4也是没有前驱的节点,可以输出4,并且删除4有关的边
然后选择6节点,输出6节点并且删除6有关的边
然后选择节点5
最后输出2和3
所以我们拓扑排序的结果就是:1->4->6->5->2->3
代码实现
Kahn算法
Kahn的算法的思路其实就是我们之前那个手动展示的拓扑排序的实现,我们先使用一个栈保存入度为0 的顶点,然后输出栈顶元素并且将和栈顶元素有关的边删除,减少和栈顶元素有关的顶点的入度数量并且把入度减少到0的顶点也入栈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| bool Graph_DG::topological_sort() { cout << "图的拓扑序列为:" << endl; stack<int> s; int i; ArcNode * temp; for (i = 0; i != this->vexnum; i++) { temp = this->arc[i].firstarc; while (temp) { ++this->indegree[temp->adjvex]; temp = temp->next; }
}
for (i = 0; i != this->vexnum; i++) { if (!indegree[i]) { s.push(i); } } 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])) { s.push(temp->adjvex); } temp = temp->next; } ++count; } if (count == this->vexnum) { cout << endl; return true; } cout << "此图有环,无拓扑序列" << endl; return false; }
|
DFS算法
它每次都沿着一条路径一直往下搜索,知道某个顶点没有了出度时,就停止递归,往回走,所以我们就用DFS的这个思路,我们可以得到一个有向无环图的拓扑序列,其实DFS很像Kahn算法的逆过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| bool Graph_DG::topological_sort_by_dfs() { stack<string> result; int i; bool * visit = new bool[this->vexnum]; memset(visit, 0, this->vexnum); cout << "基于DFS的拓扑排序为:" << endl; for (i = 0; i < this->vexnum; i++) { if (!visit[i]) { dfs(i, visit, result); } } 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; } result.push(this->arc[n].data);
}
|
总结
对于基于DFS的算法,增加结果集的条件是:顶点的出度为0。这个条件和Kahn算法中入度为0的顶点集合似乎有着异曲同工之妙,Kahn算法不须要检测图是否为DAG,假设图为DAG,那么在入度为0的栈为空之后,图中还存在没有被移除的边,这就说明了图中存在环路。而基于DFS的算法须要首先确定图为DAG,当然也可以做出适当调整,让环路的检测測和拓扑排序同一时候进行,毕竟环路检測也可以在DFS的基础上进行。
结束
2127. 参加会议的最多员工数