拓扑排序

灯珑LoGin

发布于 2022-10-31 13:13:53

4040

发布于 2022-10-31 13:13:53

文章被收录于专栏：龙进的专栏

有向无环图可以用来表示各种事物的顺序，比如工作顺序。一些事情必须在另一些事情完成之后才能开始进行。那么，为了获得正确的工作顺序（一件事情开始之前，必须保证它的前置条件全部满足），就需要用到拓扑排序。

拓扑排序其实就是在有向无环图中，只要存在边(u,v)，那就让u排在v前面。

我们可以通过广度优先搜索或者深度优先搜索来实现拓扑排序。

广度优先的思路就是对每个入度为0的且未被访问过的节点进行广度优先搜索。

在搜索过程中，只要搜索了u与v之间的边，那就将v的入度减1，相当于删除边的操作。入度为零就代表着它的前置条件已经完全满足。一个节点只有当其入度为0且未被访问过，才对其进行广度优先搜索。

下面是通过bfs拓扑排序的伪代码

利用DFS进行拓扑排序的思路相对简单，就是循环以当前仍未搜索的节点为起点，进行dfs，然后逆序把节点id存入列表中。但是，对于大规模的图来说，深度优先搜索很容易栈溢出，并且由于递归调用有开销，所以，采用BFS会更好。

对于题目 GRL_4_B ，采用BFS的AC代码如下

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXV 10005


vector<int> vec[MAXV];
vector<int> ans;

int v, e;

int indeg[MAXV] = {0};
bool vis[MAXV] = {false};

void bfs(int u)
{
    queue<int>q;
    vis[u] = true;
    q.push(u);

    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        ans.push_back(t);
        for(int x:vec[t])
        {
            indeg[x]--;
            if(indeg[x]==0&&vis[x]==false)
            {
                q.push(x);
                vis[x] = true;

            }
        }
    }
}

void solve()
{
    for (int i = 0; i < v; ++i)
    {
        if (indeg[i] == 0 && vis[i] == false)
        {
            bfs(i);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> v >> e;

    int s, t;
    for (int i = 0; i < e; ++i)
    {
        cin >> s >> t;
        vec[s].push_back(t);
        indeg[t]++;
    }
    solve();
    for(int x:ans)
    {
        cout<<x<<endl;
    }
}

转载请注明来源：https://www.longjin666.top/?p=762

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年1月31日2，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs