有关于拓扑排序的整合

拓扑排序 很简单的知识点 但是我想记录一下我见过的题型和解决方法。

这是摘抄自More study needed.的一段对拓扑排序的理解：

其实说白了，拓扑排序就是一个广度优先搜索。

方法如下：

（1）从邮箱图中选择一个没有前驱（即入度为0）的顶点并且输出它。

（2）从网中删除该顶点，并且删去从该点出发的全部有向边。

（3）重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。

1.题型一：输出任意的一个拓扑排序。

方法一：利用优先队列的方法。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>using namespace std;const int maxn = 100 + 8;int n,m,x,y,cnt;int ans[maxn],ind[maxn];void see(vector<int> v[]);void init(){    memset(ans,0,sizeof ans);    memset(ind,0,sizeof ind);    cnt = 0;}void toposort(vector<int> v[]){    PRiority_queue<int,vector<int>,greater<int>> PQ;    for(int i = 1 ; i <= n; ++i) {        if (ind[i] == 0) {//将入度为0的点加进来，并且利用优先队列从大到小排起来。            PQ.push(i);        }    }//    while(!PQ.empty())//    {//        cout << PQ.top() << endl;//        PQ.pop();////    }    while(!PQ.empty())    {        int tmp = PQ.top();        PQ.pop();        ans[cnt++] = tmp;        for(int i = 0; i < v[tmp].size(); ++i)        {            int e = v[tmp][i];            ind[e]--;            if(ind[e] == 0)            {                PQ.push(e);            }        }    }    return;}int main(){    init();    vector<int> v[maxn];    scanf("%d%d",&n,&m);    for(int i = 1; i <= m; ++i){        scanf("%d%d",&x,&y);        v[x].push_back(y);        ind[y]++;    }    //see(v);    toposort(v);    for(int i = 0; i < cnt; ++i)    {        printf("%d ",ans[i]);    }    printf("/n");    return 0;}void see(vector<int> v[]){    int num = 1;    while(!v[num].empty())    {        printf("%d : ",num);        for(int i = 0; i < v[num].size(); ++i){            printf("%d ",v[num][i]);        }        printf("/n");        num++;    }    return;}
方法二：利用邻接矩阵的方法。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>using namespace std;const int maxn = 100 + 8;int ans[maxn],ind[maxn];bool graph[maxn][maxn];int n,m,x,y,cnt,mark;void init(){    memset(ind,0,sizeof ind);    memset(ans,0,sizeof ans);    memset(graph,false,sizeof graph);    cnt = 0;}void toposort(){    for(int i = 1; i <= n; ++i){        for(int j = 1; j <= n; ++j){            if(ind[j] == 0){                ans[cnt++] = j;                ind[j]--;                mark = j;                break;//一旦找到 就跳出循环来。            }        }        for(int k = 1; k <=n; ++k){            if(graph[mark][k] == true){                graph[mark][k] = false;                ind[k]--;            }        }    }}int main(){    init();    scanf("%d%d",&n,&m);    for(int i = 1; i <= m; ++i)    {        scanf("%d%d",&x,&y);        if(graph[x][y] == false) {//避免重复!            graph[x][y] = true;            ind[y]++;        }    }    toposort();    for(int i = 0; i < cnt; ++i)    {        printf("%s%d",i == 0 ? "":" ", ans[i]);    }    printf("/n");    return 0;}
2.题型二：输出拓扑排序的全部路径。
方法要点：利用回溯法＋拓扑排序。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>using namespace std;const int maxn = 100 + 8;int n,m,x,y;bool graph[maxn][maxn];int indegree[maxn];int ans[maxn];bool vis[maxn];void init(){    memset(vis,0,sizeof vis);    memset(ans,0,sizeof ans);    memset(graph,false, sizeof graph);    memset(indegree,false, sizeof indegree);    //cnt = 0;}void toposort(int cnt){    if(cnt == n){        for(int i = 0; i < n; ++i){            printf("%s%d",i == 0 ? "": " ",ans[i]);        }        printf("/n");        return;    }    for(int i = 1; i <= n; ++i){        if(!indegree[i] && !vis[i]){            for(int j = 1; j <= n; ++j) {                if (graph[i][j]) {                    indegree[j]--;                }            }            ans[cnt] = i;            vis[i] = true;            toposort(cnt+1);            for(int k = 1; k <= n; ++k) {                if (graph[i][k]) {                    indegree[k]++;//利用回溯法 之前自减的再自加回来.                }            }            vis[i] = false;//利用回溯法 之前变为true的再false回来.        }    }    return;}int main(){    scanf("%d%d",&n,&m);    init();    for(int i = 1; i <= m; ++i){        scanf("%d%d",&x,&y);        graph[x][y] = true;        indegree[y] ++;    }    toposort(0);    return 0;}
－－－－－－会持续更新。