拓扑排序专项总结

拓扑排序专项总结

引用

CSDN

1.

https://blog.csdn.net/jameslhn/article/details/133797924

拓扑排序是图论中一个重要的概念，广泛应用于计算机科学和算法设计中。本文将从基本概念、构建过程、应用场景等多个维度，深入浅出地介绍拓扑排序的相关知识，并通过具体代码示例帮助读者更好地理解和掌握这一算法。

拓扑排序的基本概念

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。该序列必须满足以下两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑排序的构建过程

拓扑排序的构建过程可以概括为以下步骤：

1. 从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复上述步骤，直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。通常，一个有向无环图可以有一个或多个拓扑排序序列。

拓扑排序的应用场景

状态单向转移，形成拓扑序

拓扑序可以决定动态规划（DP）的顺序，而拓扑排序则是用于求图上的点的拓扑序。对于图上任意两点 x，y （x≠y)，当 x 的拓扑序大于 y的拓扑序时，x 不能到达 y。因此，在有向有环图和无向图上是不存在拓扑序的。而拓扑排序则是用于求 DAG(有向无环图)的拓扑序。

拓扑排序的代码实现

下面是一个经典的拓扑排序算法实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, x, b[110];
vector<int> g[110];
queue<int> q;

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    while (cin >> x && x) {
      g[i].push_back(x), b[x]++;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!b[i]) {
      q.push(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    x = q.front();
    q.pop();
    cout << x << ' ';
    for (int j : g[x]) {
      b[j]--;
      if (!b[j]) {
        q.push(j);
      }
    }
  }
  return 0;
}

拓扑排序的实际应用案例

拓扑排序在实际问题中有着广泛的应用，例如：

1. 图上动态规划：拓扑序决定了 DP 的顺序，因此当要做图上 DP 时可以直接边拓扑排序边 DP。
2. 判环：给定一个有向图，可以通过拓扑排序来判环，当拓扑排序后仍有节点没有被规定拓扑序时就是有环。

下面是一个结合动态规划、拓扑序和博弈论的实际应用案例：

#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
using namespace std;
const int N = 1E5+20;
int n,dp[N],A[N];
vector<int > vec[N];
int dfs(int x)
{
    if(dp[x]!=-1) return dp[x];
    int defa=0;
    for(int i=0;i<vec[x].size();i++)
    {
        if(!dfs(vec[x][i]))
        {
        	defa=1;
        	break;
        }
    }
    return dp[x]=defa;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
       cin>>A[i];
    char c[N];
    for(int i=1;i<=n;i++)
    {
        for(int j=i+A[i];j<=n;j=j+A[i])
            if(A[j]>A[i])
               vec[i].push_back(j);
        
        for(int j=i-A[i];j>=1;j=j-A[i])
            if(A[j]>A[i])
               vec[i].push_back(j);
    }
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)
        if(dp[i]==-1) dfs(i);
    for(int i=1;i<=n;i++)
        cout<<(dp[i]==1?'A':'B');//dp[i]=1代表必胜态 ,dp[i]代表必败态 
    return 0;
}

通过以上内容，相信读者已经对拓扑排序有了全面的了解。拓扑排序不仅是一个重要的算法概念，更是在实际问题中有着广泛的应用价值。希望本文能够帮助读者更好地掌握这一算法，并在实际开发中灵活运用。