図の拡張ソート基本アルゴリズム

トポロジーソートは簡単で、1つの図に存在する(u,v)ことで、uはvの前に遍歴しなければならないが、アルゴリズムはトポロジー順に図を遍歴する.例えば、大学の課程のように、ある課程aは課程bの先修課程であり、すなわち、aを先に勉強しなければb課程を学ぶことができず、拡張アルゴリズムで1つの課程の手配順序を合理的に与えることができる.注意図にループは存在しません.そうしないと、拡張ソートに失敗します.基本アルゴリズムは次のとおりです.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
const int maxn = 100 + 5;

int n, m;
int G[maxn][maxn], inDgree[maxn];
vector<int> ans;

bool topoSort() {
    queue<int> q;
    int cnt = 0;

    for(int i = 0; i < n; i++)
        if(inDgree[i] == 0)     q.push(i);  //      0      

    while(!q.empty()) {
        int u = q.front();  q.pop();
        ans.push_back(u);
        cnt++;
        for(int i = 0; i < n; i++)
            if(G[u][i]) {
                G[u][i] = 0;
                if(--inDgree[i] == 0)   q.push(i);
            }

    }

    if(cnt != n)    return false;
    else              return true;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >>m;
    memset(G, 0, sizeof(G));
    memset(inDgree, 0, sizeof(inDgree));

    int u, v;
    for(int i = 0; i < m; i++) {
        cin >> u >> v;
        G[u][v] = 1;      inDgree[v]++;
    }

    ans.clear();
    if(topoSort()) {
        printf("%d", ans[0]);
        for(int i = 1; i < ans.size(); i++)     printf("-->%d", ans[i]);
        printf("
");
    }
    else    printf("Error ! there is a circle in the graph!!");



    return 0;
}