BFS实现拓扑排序的方法:

策略:

用一个队列来维护当前所有入度为0的点,
每次任取一个点作为当前拓扑序列的点然后将其删除,
然后,更新其余点的入度,如果相继的点因为上一个点删除而入度为0,
则继续迭代以上操作即可

判定:

通过一系列删除过程,最后删除到如果没有结点了,那么这个图就判定有拓扑序列
如果最后还剩下结点无法删除则判定为没用拓扑序列

基于BFS时间复杂度为O(n+m),整个过程是每个点和每条边都只会被遍历一次所以是线性复杂度

在实际算法代码实现中,时间复杂度在于你用什么样的存储方式,邻接表的话就是O(n+m),邻接矩阵则是O(n^2)

代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;

struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int d[N],q[N];

void add(int a,int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1;i <= n;i ++)
        if(!d[i])
            q[++ tt] = i;

    while(hh <= tt)
    {
        int t = q[hh ++];
        for(auto p = head[t]; p ;p = p->next)
            if(-- d[p->id] == 0)
                q[++ tt] = p->id;
    }
    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d",&a,&b);
        d[b] ++;
        add(a, b);
    }

    if(!topsort())  printf("-1");
    else
    {
        for (int i = 0; i < n; i ++ )
            printf("%d ",q[i]);
    }

    return 0;
}

DFS实现拓扑排序

策略:回溯

利用DFS对每一个结点的遍历之后,到最后一个结点开始回溯的时候说明前面所有点已经遍历全部过了,因此在回溯前打印可输出拓扑的逆序列

直接在回溯的时候把逆向的拓扑序列存储起来反向输出即可,如下(但是要注意!这只是过程不是结果,我们还要讨论是否存在拓扑序列的问题)

void dfs(int u)
{
    st[u] = true;

    for (auto p = head[u]; p ;p = p->next)
    {
        int j = p->id;
        if(!st[j])
            dfs(j);
    }

    printf("%d ",u);
}

接下来就是判定是否存在拓扑序列

其实很简单,只需要在DFS过程中记录递归路径当中的所有结点,如果继续往下深搜的时候,搜到递归路径上的结点,则就表明有环的存在,只要存在环,就不可能存在拓扑序列

具体操作就是直接把st数组约定0是没搜到,1是在搜的路径中,2是已经搜过回溯了就解决了!

基于深搜的代码一定要遍历一下所有点,防止图存在不连通情况

时间复杂度O(n+m)

代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;

struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int st[N],q[N],top;

void add(int a,int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool dfs(int u)
{
    st[u] = 1;

    for (auto p = head[u]; p ;p = p->next)
    {
        int j = p->id;
        if(!st[j])//是0直接搜
        {
            if(!dfs(j))//往下搜的过程中如果发现是环
                return false;
        }
        else if(st[j] == 1) return false;
    }

    q[top ++] = u;//用个数组记录结果
    st[u] = 2;
    return true;
}

bool topsort()
{
    for (int i = 1; i <= n; i ++ )
        if(!st[i] && !dfs(i))
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d",&a,&b);
        add(a, b);
    }

    if(!topsort())  puts("-1");
    else
    {
        for(int i = n - 1;i >= 0;i --)
            printf("%d ", q[i]);
    }

    return 0;
}