拓扑排序

拓扑排序

从离散数学的角度定义，假设(A,≤)是有限偏序集，对其进行拓扑排序是指将其扩展成一个全序集，使得≤∈<，即对任意的a,b∈A,若a≤b,则a<b。

从图论的角度定义，对一个有向无环图G进行拓扑排序，是将G中所有的顶点排成一个线性序列，使得图中任意一对顶点u和v,如果(u,v)∈E(G),则u在线性序列中应出现在v之前。

思路

从离散数学的角度定义，拓扑排序是针对有限偏序集的，由离散数学的知识知，若(A,≤)是偏序集，则拟序集(A,<)中不存在长度大于1的环（这其实与无环图对应）,所以有限偏序集可以画成哈斯(Hasse)图。Hasse图非空时总存在极小元，每次输出极小元，更新Hasse图，直到Hasse为空。

从图论的角度，极小元等同于图中入度为0的顶点，每次输出入度为0的点，更新与之相连点的入度，直到输出全部顶点。如果存在顶点没有输出，说明存在环。

样题

给任务排序(UVa10305)

假设有n个任务，还有m个二元组(u,v)，(u,v)表示u必须在v之前执行。请输出n个任务按顺序执行的一种可能情况。

代码实现

邻接矩阵+队列

#include<stdio.h>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int V = 100 + 10;            //最大顶点数
const int E = 100 * 100 + 10;    //最大边数
vector<int>e[V];        //邻接矩阵存图
int in[V];                //顶点的入度

int m, n;

int main()
{
    while (scanf("%d%d", &n, &m) == 2 && n)
    {
        for (int i = 0; i < n; i++)        
        {
            e[i].clear();
            in[i] = 0;
        }
        for (int i = 0; i < m; i++)
        {
            int from, to;
            scanf("%d%d", &from, &to);
            e[from].push_back(to);
            in[to]++;
        }
        vector<int>ans;
        queue<int>q;
        for (int i = 1; i <= n; i++)  if (!in[i])    q.push(i); //将入度为0的入队
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            ans.push_back(u);
            for (int i = 0; i < e[u].size(); i++)        //遍历与之相连的顶点
                if ((--in[e[u][i]]) == 0)  q.push(e[u][i]);    //入度减1，如果为0，入队
        }
        for (int i = 0; i < ans.size(); i++)
            printf("%d ", ans[i]);
        printf("
");
    }
    return 0;
}

 dfs

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const int maxn = 100 + 10;
vector<int>G[maxn];
int c[maxn], topo[maxn], t;
int n, m;

bool dfs(int u)
{
    c[u] = -1;    //正在访问,dfs(u)正在栈帧中，尚未返回
    for (int i = 0; i < G[u].size(); i++)
    {
        if (G[u][i])
        {
            if (c[G[u][i]] < 0) return false;
            else if (!c[G[u][i]] && !dfs(G[u][i]))    return false;
        }
    }
    c[u] = 1;    //已经访问过，dfs(u)已被调用过，并已访问
    topo[--t] = u;
    return true;
}

bool toposort()
{
    t = n;
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++)
        if (!c[i] && !dfs(i))        //c[i]为0表示从未访问过
            return false;
    return true;
}

void slove()
{
    if (toposort())
    {
        for (int i = n - 1; i >= 0; i--)
            printf("%d ", topo[i]);
        printf("
");
    }
}

int main()
{
    int u, v;
    while (scanf("%d%d", &n, &m) == 2 && n)
    {
        for (int i = 0; i <= n; i++)    G[i].clear();
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &u, &v);
            G[v].push_back(u);
        }
        slove();
    }
    return 0;
}

 参考链接：

https://baike.baidu.com/item/拓扑排序/5223807?fr=aladdin

https://blog.csdn.net/qq_41713256/article/details/80805338

中国大学mooc  刘铎  离散数学