拓扑排序
只适用于 AOV网 (有向无环图)
算法流程:
用队列来执行 ,初始化讲所有入度为0的顶点入队。
主要由以下两步循环执行,直到不存在入度为 0 的顶点为止
- 选择一个入度为 0 的顶点,并将它输出;
- 删除图中从顶点连出的所有边。
循环结束,
若输出的顶点数小于图中的顶点数,则表示该图存在回路,即无法拓扑排序,
否则,输出的就是拓扑序列 (不唯一)
模板题
Acwing 848. 有向图的拓扑序列
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,d[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 邻接表模板
// d 代表每个元素的入度
// 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(d[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];
d[j] --;// j 的入度 --
if(d[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);
while(m--){
cin >> a >> b;
add(a,b);
d[b] ++;// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1";
else {
for(int i = 1;i <= n; ++i){
cout << top[i] <<" ";
}
}
return 0;
}
“ if(cnt < n) return 0;” 错了,应该是<=
数据加强 把if(cnt < n) return 0;
else return 1; 改为return cnt - 1 == n; 即可
请问这题时间复杂度是多少
O(n+m),n是点数 m是边数
是n+1与cnt比较才出结果
邻接表基础课里面有没
其实直接看基础课数据结构的单链表就可啦
就是单链表
有个问题
int i = h[t]
这里是指的t还是t的头节点,然后为什么可以表示遍历t的出边t不就是队头吗,取出队头的点,然后在t对应的单链表h[t]里找邻接点
AOV网 != 有向无环图吧,有向无环图是DAG,包含AOV和AOE吧。
好像cnt-1是进入队列的点数
我感觉这样是对的呀QAQ:
if(cnt-1 < n) return 0;
else return 1;
只有cnt == n的时候才代表拓步排序完成,否则其他任何结果都有可能, 比如 cnt < n 只是范围更大了而已
cnt - 1 < n 可能也行吧,意思就是只入队了最多 n - 2 个节点,可能是数据问题?所以这样写也可以?,这是我个人的理解,如果有不对的地方还请指出。
博主,但是你这里cnt初值是1, 后面cnt++了, 所以队列中元素是n的时候,cnt = n +1, 最后判断应该是if(cnt < n + 1) return 0;吧
你的cnt初值是1,程序是错误的,比如样例 2 2
1 2
2 2
应该先判cnt为0 , 在to【++cnt】
真的耶,为啥呀
因为cnt记录的已经遍历出的答案,我们为了完成拓扑排序应该将所有的n个点都遍历出来,如果有任一一个点没有遍历出来都代表没有完成,也就是出现了环结构
我好像懂了,谢谢大佬!!