拓扑排序

2023-12-29 19:37:07

拓扑排序

先引入度数的概念:

度数=入度+出度

  1. 入度:有多少条边指向自己。
  2. 出度:有多少条边从自己指出。

啥是拓扑排序?

一个有向图,如果图中有入度为 0 的点,就把这个点删掉,同时也删掉这个点所连的边。

一直进行上面出处理,如果所有点都能被删掉,则这个图可以进行拓扑排序。

解题思路

  1. 记录各个点的入度
  2. 然后将入度为 0 的点放入队列
  3. 将队列里的点依次出队列,然后找出所有出队列这个点发出的边,删除边,同事边的另一侧的点的入度 -1
  4. 如果所有点都进过队列,则可以拓扑排序,输出所有顶点。否则输出-1,代表不可以进行拓扑排序。

代码部分:

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int e[N],ne[N],idx;//邻接表存储图
int h[N];
int q[N],hh,tt=-1;//队列保存入度为0的点,也就是能够输出的点,
int n,m;//保存图的点数和边数
int d[N];保存各个点的入度
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort(){
    for(int i=1;i<=n;i++){//遍历一遍顶点的入度。
        if(d[i]==0)//如果入度为 0, 则可以入队列
            q[++tt]=i;
    }
    while(tt >= hh){//循环处理队列中点的
        int a = q[hh++];
        for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
            int b = e[i];//a 有一条边指向b
            d[b]--;//删除边后,b的入度减1
            if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出,入队列
                q[++tt] = b;
        }
    }
    if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同,则可以进行拓扑排序
        for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点,依次输出
            cout << q[i] << " ";
        }
    }
    else//如果队列中的点的个数与图中点的个数不相同,则可以进行拓扑排序
        cout << -1;//输出-1,代表错误
}
int main(){
    cin >> n >> m;//保存点的个数和边的个数
    memset(h,-1,sizeof h);//初始化邻接矩阵
    while(m--){//依次读入边
        int a,b;
        cin>>a>>b;
        d[b]++;//顶点b的入度+1
        add(a,b);//添加到邻接矩阵
    }
    topsort();//进行拓扑排序
}

文章来源:https://blog.csdn.net/2301_76869282/article/details/135296852
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。