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

拓扑排序其实就是在有向无环图中,只要存在边(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

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论