bfs拓扑排序

拓扑排序

bfs做法

我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 u：

我们将 u 放入答案中；

我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 00，那么我们就将 v 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

一、基本概念

对于一有向无环图（DAG），对图中的所有节点进行排序，使图中的所有边，其起点在点序列中都在终点的前面——这个排序过程称之为拓扑排序。

拓扑排序出的序列并不唯一，对于同一张图可能有很多个序列满足以上的条件。

拓扑排序常用于解决有向图中的依赖解析问题。

也就是说，像“做A任务时必须先完成B任务”这样的限制条件，通过拓扑排序能够得到一个满足执行顺序的序列。

当不存在满足条件的序列时，也就代表图中出现了环，形成了循环依赖的情况。

循环依赖的意思是：做A任务必须先完成B任务，但做B任务也必须先完成A任务。则此时对于问题是无解的。

二、算法思想

常用的拓扑排序算法是通过BFS（广度优先搜索）来实现的，具体步骤如下。

• 对于每个点，我们都需要记录它的入度。
• 将入度为0的节点全部加入队列。
• 取出队列的首节点，将以该节点为起点的边删去，同时将边终点的入度-1，若此时终点的入度变为0，则加入队列。
• 持续执行第3步，直至所有节点都遍历完。
• 若直到队列清空，仍有节点未遍历到，说明图内有环，无解。

该算法的时间复杂度为 O(n+m),n是顶点数，m是边数 。

三、代码实现

int in[n];//储存入度
queue<int>q;//BFS队列
vector<int>edge[n];//储存边
vector<int>ans;//最终排序后的序列
void Topological_Order()
{
    for(int i=0;i<n;i++)
        if(in[i]==0) q.push(i);//如果入度为0，加入队列
    while(!q.empty())
    {
        int f=q.front();
        q.pop();//取出队列头节点
        ans.push_back(f);//加入答案
        for(int i=0;i<edge[f].size();i++)//遍历所有以头节点为起点的边
        {
            in[edge[f][i]]--;//将终点入度-1
            if(in[edge[f][i]]==0) q.push(edge[f][i]);
            //若入度变为0，加入队列
        }
    }
    if(ans.size()!=n) cout<<"No Solution"<<endl;
    //若答案序列的长度不为n，说明有节点未遍历到，则无解
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Kahn算法

上面就是kahn算法。

拓扑排序是对DAG（有向无环图）上的节点进行排序，使得对于每一条有向边 u->v ， u 都在 v 之前出现。简单地说，是在不破坏节点先后顺序的前提下，把DAG拉成一条链。

拓扑排序最经典的算法是Kahn算法。首先，先拿出所有入度为0的点排在前面，并在原图中将它们删除：

这时有些点的入度减少了，于是再拿出当前所有入度为0的点放在已经排序的序列后面，然后删除：

因为是有向无环图，而且删除操作不会产生环，所以每时每刻都一定存在入度为0的点，一定可以不断进行下去，直到所有点被删除。

以下是一个 O(n+m) 的实现（ n,m 分别表示点数和边数），利用了队列：

// deg是入度，在存图的时候需要录入数据
// A是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort(int n)
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        A[cnt++] = t;
        for (auto to : edges[t])
        {
            deg[to]--;
            if (deg[to] == 0) // 出现了新的入度为0的点
                q.push(to);
        }
    }
    return cnt == n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

返回值为是否成功进行拓扑排序，也即是否存在环。也就是说拓扑排序是可以用来简单地判环的。有时会要求输出字典序最小的方案，这时把queue改成priority_queue即可，复杂度会多一个 log 。