欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑排序

程序员文章站 2023-12-23 17:11:10
...

在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。

先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。

一直做改操作,直到所有的节点都被分离出来。

如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。

下面是算法的演示过程。

拓扑排序
模板

vector

//重环无影响
const int maxn = 1e5 + 7;
std::vector<int> G[maxn];
queue<int>q;
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
bool topsort(){
    while(!q.empty()) q.pop();
    for(int i = 1;i <= n ; i++) if(!inDeg[i]) q.push(i);
    while(!q.empty()){
        int now = q.front()//q.top();
        q.pop();
        for(int i = 0 ; i < G[now].size(); i++){
            if(--G[now][i] == 0)
                q.push(G[now][i]);
        }
    }    
}

前向星

const int maxn = 1e5 + 7;
struct edge
{
    int to,nxt;
}e[maxn << 1];
int head[maxn];
int tot;
void add_adge(int u , int v){
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot++;
}
queue<int>q;
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
bool topsort(){
    while(!q.empty()) q.pop();
    for(int i = 1;i <= n ; i++) if(!inDeg[i]) q.push(i);
    while(!q.empty()){
        int now = q.front()//q.top();
        q.pop();
        for(int i = head[now] ; i ; i = e[i].nxt){
            if(--e[i].to == 0)
                q.push(e[i].to);
        }
    }    
}


上一篇:

下一篇: