拓扑排序—-Kahn算法和字典序最小的拓扑排序

大家好，欢迎来到IT知识分享网。

一、拓扑排序定义：

二、卡恩算法(Kahn):

1、Kahn算法介绍：

有向无环图DAG至少具有一个度数为0的顶点和一个度数为0的顶点。
证明：上述事实有一个简单的证明，即DAG不包含循环，这意味着所有路径的长度都是有限的。现在，使S为从u（源）到v（目标）的最长路径。由于S是最长的路径，因此不会有到u的传入边缘，也不会有从v的传出边缘，因此，如果发生这种情况，则S不会是最长的路径
=> indegree（u）= 0且outdegree（v）= 0

2、查找DAG的拓扑顺序涉及的步骤：

步骤1：为DAG中存在的每个顶点计算入度（传入边数），并将访问节点的计数初始化为0。
步骤2：选取度数为0的所有顶点并将其添加到队列中（入队操作）
步骤3：然后从队列中删除一个顶点（出队操作）。访问的节点数增加1。将其所有相邻节点的度数减少1。如果相邻节点的入度减小到零，则将其添加到队列中。
步骤4：重复步骤3，直到队列为空。
步骤5：如果访问的节点数小于图中的节点数，则对于给定的图，不可能进行拓扑排序。

2、Kahn算法的伪代码：

L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edge while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order) 

3、代码：

#include<iostream> #include<list> #include<vector> #include<queue> using namespace std; class Graph { 
    int n; //顶点数 list<int> *adj; //邻接表  public: Graph(int _n) { 
    n = _n; adj = new list<int>[_n];} ~Graph(){ 
    delete [] adj; } void addEdge(int v, int w){ 
    adj[v].push_back(w); } void topologicalSort(); }; 

void Graph::topologicalSort() { 
    vector<int> indegree(n,0); for(int i = 0; i < n; i++) { 
    list<int>::iterator it; for(it = adj[i].begin(); it != adj[i].end(); it++) { 
    indegree[*it]++; //邻居的入度+1  } } queue<int> q; for(int i = 0; i < n; i++) //入度为0的顶点先进队列 { 
    if(indegree[i] == 0) { 
    q.push(i); } } vector<int> topologicalOrder; //存排好序的拓扑排序 while(!q.empty()) { 
    int u = q.front(); q.pop(); topologicalOrder.push_back(u); list<int>::iterator it; for(it = adj[u].begin(); it != adj[u].end(); it++) { 
    indegree[*it]--; if(indegree[*it] == 0) { 
   //新的入度为0的顶点加入队列 q.push(*it); } } } if(topologicalOrder.size() < n) { 
    cout<<"这个图有环"<<endl; return ; } for(int i = 0; i < topologicalOrder.size(); i++) { 
    cout<<topologicalOrder[i]<<" "; } cout<<endl; } 

int main() { 
    Graph g(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); cout << "这个图的拓扑排序是：\n"; g.topologicalSort(); return 0; } 

4、理解：

Kahn算法，主要就是利用了“有向无环图DAG至少具有一个度数为0的顶点和一个度数为0的顶点”的原理(上面有证明），因为入度为0的顶点在拓扑排序里要排在有入度的前面，然后利用队列先进先出的特点，先把入度为0的顶点排前，一轮一轮地加入新的入度为0的顶点(它的所有的父顶点把到它的边删了)，然后就排好序了。
为什么if(topologicalOrder.size() < n) { cout<<"这个图有环"<<endl; return ; } ?
因为当有环时，必然有顶点因为入度不为0而不能进队列，导致得到的拓扑排序里的顶点数小于图的顶点数。

5、字典序最小的拓扑排序：

把队列改成优先队列就能实现了。

#include<iostream> #include<list> #include<vector> #include<queue> using namespace std; class Graph { int n; //顶点数 list<int> *adj; //邻接表 public: Graph(int _n) { n = _n; adj = new list<int>[_n];} ~Graph(){ delete [] adj; } void addEdge(int v, int w){ adj[v].push_back(w); } void topologicalSort(); }; void Graph::topologicalSort() { vector<int> indegree(n,0); for(int i = 0; i < n; i++) { list<int>::iterator it; for(it = adj[i].begin(); it != adj[i].end(); it++) { indegree[*it]++; //邻居的入度+1 } } priority_queue<int, vector<int>,greater<int>> q; //优先队列从小到大 for(int i = 0; i < n; i++) { if(indegree[i] == 0) { q.push(i); } } vector<int> topologicalOrder; while(!q.empty()) { int u = q.top(); q.pop(); topologicalOrder.push_back(u); list<int>::iterator it; for(it = adj[u].begin(); it != adj[u].end(); it++) { indegree[*it]--; if(indegree[*it] == 0) { q.push(*it); } } } if(topologicalOrder.size() != n) { cout<<"这个图有环"<<endl; return ; } for(int i = 0; i < topologicalOrder.size(); i++) { cout<<topologicalOrder[i]<<" "; } cout<<endl; } int main() { Graph g(6); g.addEdge(4, 2); g.addEdge(4, 0); g.addEdge(5, 0); g.addEdge(5, 1); g.addEdge(2, 3); g.addEdge(3, 1); cout << "这个图的拓扑排序是：\n"; g.topologicalSort(); return 0; } 

输入换个图：

不用优先队列：

用优先队列：