拓扑排序

拓扑排序

toposort

前置知识

1. DAG ：有向无环图

2.AOV网，AOE网

这两个概念都是用来描述和分析一项工程的计划和实施过程的。注意都是有向图。

（1）AOV:Activity On Vertex Network，把每个顶点作为一项活动，把两个顶点间的边作为活动间的相互关系。看下面的例子：

活动1,2,3可以直接开始，但活动4必须在3完成后开始，5必须在1,2,3都完成后开始，6必须在1,2,5完成后开始。

（2）AOE:Activity On Edge Network，把每条边作为一项活动，通常还会有权值（长度），把每个顶点作为作为一种状态，所以只会有一个起点和一个终点。看下面的例子：

从1开始，在时刻3可以到达2，但想要到达3，必须两个指向它的边都完成，所以在时刻5可以到达3。以此类推。

3.度

一个点连着的边的数量，称为该点的度。其中由该点出发的称为出度，到达该点的称为入度。

拓扑排序

基本概念

对于一个DAG，请给定一个所有结点的排列，使得图中每条边的起点都比终点在该排列中的位置靠前。

实质作用是给AOV网或AOE网给定一个可行的完成任务的先后顺序（此处假定一个时刻只能完成一个任务）。

代码实现

BFS实现

1. 把所有入度为0的点入队

2. 循环直到队列为空

3. 队首元素h出队，并加入拓扑序

4. 对h所有可以到达的点，入度减一，若这时该点入度为零，让它入队

5. 若循环结束时拓扑序长度不为节点个数，则证明图中有环，即不是DAG，意味着不存在拓扑序，这时（在大部分情况下），你应该输出无解

JUST LIKE THIS

0 2 入度为零，先开始分离它们，也就是把他们的出边去掉

最后他们就都给分离完了，都搁这飘着

但是你如果遇到一个环

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000;
int n,m;
int head[maxn],next[maxn],in[maxn],to[maxn],cnt=0;
int ans[maxn],cntans=0;

void add(int start,int end)
{
    cnt++;
    to[cnt]=end;
    next[cnt]=head[start];
    head[start]=cnt;
    
}

int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        in[v]++;
    } 
    
    priority_queue<int,vector<int>,greater<int> >q;
    
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) q.push(i);
    }
    
    while(!q.empty())
    {
        int now=q.top();
        q.pop();
        ans[++cntans]=now;
        for(int e=head[now];e;e=next[e])
        {
            in[to[e]]--;
            if(!in[to[e]])
            q.push(to[e]);
        }
    }
    
    if(cntans!=n) printf("I AKIOI !!!");
    else
    {
        for(int i=1;i<=cntans;i++)
          printf("%d
",ans[i]);
    }
    
    return 0;
}

DFS实现 <liao jie yi xia pa>

这个算法看起来很简单，但实际却不好写。

1.从某个入度为0的点出发DFS

2.递归处理所有可以到达的点

3.将该点加入拓扑序

4.全部DFS结束后，将求出来的序列翻转，即为拓扑序

代码

#include <bits/stdc++.h>
using namespace std;
const int max_n = 100001, max_m = 100001;
int fir[max_n], to[2 * max_m], nxt[2 * max_m], ecnt;
void add(int u, int v)
{
    to[++ecnt] = v;
    nxt[ecnt] = fir[u];
    fir[u] = ecnt;
}
int in[max_n];
int n, m;
int ans[max_n], anscnt;
int vis[max_n]; //0:not visited  1:visited  -1:is visiting
bool dfs(int node)
{
    vis[node] = -1;
    for (int e = fir[node]; e; e = nxt[e])
    {
        if (vis[to[e]] == 1)
            continue;
        if (vis[to[e]] == -1 || dfs(to[e]) == false)
            return false;
    }
    vis[node] = 1;
    ans[++anscnt] = node;
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        in[v]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0 && vis[i] == 0)
        {
            if (dfs(i) == false)
            {
                break;
            }
        }
    }
    if (anscnt != n)
    {
        cout << "I AKIOI !!!
";
    }
    else
    {
        for (int i = n; i >= 1; i--)
        {
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
}

最后安利一个画图网站：

https://csacademy.com/app/graph_editor/

QWQ 画出来是一个会游动的图它很皮

最最后感谢 water lift 的讲解以及课件和代码QWQ