数据结构与算法学习笔记----拓扑排序

数据结构与算法学习笔记----拓扑排序

@@ author: 明月清了个风
@@ first publish time: 2024.12.10

拓扑排序

拓扑排序是一个有向无环图，需要满足的条件是：若存在一条从顶点$A$指向顶点$B$的路径，那么在拓扑序列中$A$出现在$B$前面。

BFS用来求拓扑序列很方便，因为BFS强调层级的概念，在图论中，入度和出度是描述有向图顶点的重要属性，而在拓扑序列中，我们就是使用顶点的入度进行BFS的。

对于一个顶点$B$来说，如果他有入度，那么必有另一个顶点$A$通过一条边指向它，并且顶点$A$在拓扑排序中在它之前，那么我们可以将所有入度为$0$的点入队，因为没有任何边指向他们，所以他们可以在拓扑排序中排在前面，然后进行BFS，在BFS的过程中逐步减去每个被遍历到的点的入度，入度为$0$的点继续入队，完成遍历。

至于是否有环的判断，就看最后的拓扑序列中是否所有点都入队了，下面是一道模版题，可以看一下代码的处理。

Acwing 848. 有向图的拓扑序列

[原题链接](848. 有向图的拓扑序列 - AcWing题库)

给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出$-1$。

若一个由图中所有点构成的序列$A$满足：对于图中的每条边$(x,y)$，$x$在$A$中都出现在$y$之前，则称$A$是该图的一个拓扑序列。

输入格式

第一行包含两个整数$n$和$m$。

接下来$m$行，每行包含两个整数$x$和$y$，表示存在一条从$x$走到$y$的有向边$(x,y)$。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出$-1$。

数据范围

$1\le n,m\le 10^5$

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];  // 记录每个点的入度，也就是有多少条边指向该点，
int q[N], hh, tt = -1;  // 因为最后要输出拓扑排序，用数组模拟队列，BFS模版用的是queue

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}


bool topsort()
{
    for(int i = 1; i <= n; i ++)   // 首先将所有入度为0的点入队。
        if(!d[i]) q[++ tt] = i;
        
    while(hh <= tt)   // 队列中有元素
    {
        int t = q[hh ++];
        
        for(int i = h[t]; i != -1; i = ne[i])   //  BFS搜索
        {
            int j = e[i];
            d[j] --;    // 搜到一个点，将该点入度减1.
            if(d[j] == 0) q[++ tt] = j;  // 如果为0，那就入队
        }
    }
    
    return tt == n - 1;   // 判断最后是否是n个顶点都入队了。
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);   // 初始化单链表队头
    
    for(int i = 0; i < m; i ++)   // 读入所有的边。
    {
        int a, b;
        cin >> a >> b;
        d[b] ++;   // b点的入度加1
        add(a, b);
    }

    if(topsort())   
    {
        for(int i = 0; i < n; i ++)
            cout << q[i] << ' ';
        cout << endl;
    }
    else cout << "-1" << endl;
    
    
    return 0;
}

原文地址：https://blog.csdn.net/weixin_60278491/article/details/144385123

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！