C++拓扑排序
quicklsleap 人气:2一、前言
且该序列必须满足下面两个条件:
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 x到顶点 y的路径,那么在序列中顶点 x 出现在顶点 y的前面。
拓扑排序只适用于 AOV网 (有向无环图)
若图中有环,则一定不存在拓扑序。
可以证明,一个有向无环图,一定存在一个拓扑序列。有向无环图,又被称为拓扑图。
入度: 即有多少条边指向自己这个节点。
出度: 即有多少条边从自己这个节点指出去。
二、算法流程
算法流程:
用队列来执行 ,初始化所有入度为0的顶点入队。
主要由以下两步循环执行,直到不存在入度为 0 的顶点为止
选择一个入度为 0 的顶点,并将它输出;
删除图中从顶点连出的所有边
循环结束
若输出的顶点数小于图中的顶点数,则表示该图存在回路,即无法拓扑排序,
否则,输出的就是拓扑序列 (不唯一)
模板如下:
1.数组模拟队列实现拓扑排序
bool topsort() { int hh = 0, tt = -1; // in[i] 存储点i的入度 for (int i = 1; i <= n; i ++ )// 将所有入度为0的点加入队列 if (in[i]==0) top[ ++ tt] = i; while (hh <= tt) { int t = top[hh ++ ];//找到入度为0的队头 //遍历一下以t为头节点的的单链表,给每一个结点都要减去1,并再次找到入度为0的点 for (int i = h[t]; i != -1; i = ne[i]) { // 遍历 t 点的出边 int j = e[i]; if (-- in[j] == 0)//将入度减1,如果 j 入度为0,加入队列当中 top[ ++ tt] = j; } } // 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。 return tt == n - 1; }
2.使用STL queue实现拓扑排序
bool topsort(){ queue<int> q; int t; for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列 if(in[i] == 0) q.push(i); while(q.size()){ t = q.front();//每次取出队列的首部 top[cnt] = t;//加入到 拓扑序列中 cnt ++; // 序列中的元素 ++ q.pop(); for(int i = h[t];i != -1; i = ne[i]){ // 遍历 t 点的出边 int j = e[i]; in[j] --;// j 的入度 -- if(in[j] == 0) q.push(j); //如果 j 入度为0,加入队列当中 } } if(cnt < n) return 0; else return 1; }
时间复杂度 O(n+m), n表示点数,m表示边数
三、有向图的拓扑排序
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
思路
我们每次找到入读为0的点,然后把他插入到队列里,然后将这个点删除,这也就意味着这个点连接的下一个点(可能是多个)的入度就会减1。
这个时候,我们就进入了下一轮。
我们因为前面将一个点删除了,那么它指向的点的入度就会都减去1,所以,就会出现新的点的入度为0,这个点显然是因为它的入度小,所以它理所应当的排在拓扑序里面在第二位。当前面的一个点没有了被删除了,那它就要首当其冲了。
和图的BFS思路很像,但是加了搜索的规则(即入度为零的先被搜索)可以看点这里
AC代码
#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 1e5 + 10; int e[N],ne[N],h[N],idx,in[N],n,m,top[N],cnt = 1; // e,ne,h,idx 邻接表模板 // in 代表每个元素的入度 // top是拓扑排序的序列,cnt代表top中有多少个元素 void add(int a,int b){ e[idx] = b; ne[idx] = h[a];h[a] = idx ++; } bool topsort(){ queue<int> q; int t; for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列 if(in[i] == 0) q.push(i); while(q.size()){ t = q.front();//每次取出队列的首部 top[cnt] = t;//加入到 拓扑序列中 cnt ++; // 序列中的元素 ++ q.pop(); for(int i = h[t];i != -1; i = ne[i]){ // 遍历 t 点的出边 int j = e[i]; in[j] --;// j 的入度 -- if(in[j] == 0) q.push(j); //如果 j 入度为0,加入队列当中 } } if(cnt < n) return 0; else return 1; } int main(){ int a,b; cin >> n >> m; memset(h,-1,sizeof h);//给头节点赋值为-1; while(m--){ cin >> a >> b; add(a,b); in[b] ++;// a -> b , b的入度++ } if(topsort() == 0) cout << "-1"; else { for(int i = 1;i <= n; ++i){ cout << top[i] <<" "; } } return 0; }
加载全部内容