拓扑排序(算法模板)

有一个有向图（AOV网）如下:

遍历方法:
每次找入度为0的节点，找到后删除该节点和该节点的出度边.
在新的AOV网中(删除某些节点和边后) 重复这个过程

在这个图中遍历为
第一步: 0
第二步: 1 或 2
第三步: 4
第四步:3 或 6
第五步:5
第六步:7
共有4种不同拓扑序列

拓扑序列反映那些工程得先完成，那些工程得后完成。

代码:

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

/***************类声明*********/ 
class Graph
{
    int V;  //顶点个数
    list<int> *adj; //邻接表 
    queue<int> q;   //维护一个入度为0的顶点的集合 
    int* indegree;   // 记录每个顶点的入度 

    public:
        Graph(int V);  //构造函数
        ~Graph();    //析构函数
        void addEdge(int v,int w); //添加边
        bool topological_sort();  //拓扑排序
};
/***********类定义****************/ 
Graph::Graph(int V)
{
    this->V=V;
    adj = new list<int>[V];  
    indegree = new int [V]; //入度全部初始化为0
    for(int i=0;i<V;i++) 
        indegree[i]=0;
}
Graph::~Graph()
{
    delete [] adj;
    delete [] indegree; 
}
void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
    ++indegree[w];
}
bool Graph::topological_sort()
{
    for(int i=0;i<V;i++)
        if(indegree[i]==0)
            q.push(i); //将所有入度为0的顶点入队 
    int count=0;   //计数，记录当前已经输出的顶点数
    while(!q.empty())
    {
        int v=q.front();  //从队列中取出一个顶点
        q.pop();
        cout<<v<<" ";
        ++count;
        //将所有v指向的顶点的入度减1，并将入度减为0的顶点入栈
        list<int>::iterator it=adj[v].begin();
        for(;it!=adj[v].end();it++)
            if(!(--indegree[*it]))
                q.push(*it); //若入度为0，则入队    
    }
    if(count < V) 
        return false;
    else 
        return true; 
}
int main(){
    Graph g(8);
    g.addEdge(0,1);
    g.addEdge(0,2);
    g.addEdge(2,4);
    g.addEdge(1,4);
    g.addEdge(1,3);
    g.addEdge(4,3);
    g.addEdge(4,5);
    g.addEdge(4,6);
    g.addEdge(3,5);
    g.addEdge(6,7);
    g.addEdge(5,7);
    g.addEdge(3,7);
    g.topological_sort();

    return 0;
}

运行结果为
0 1 2 4 3 6 5 7
验证确是拓扑排序中的一种.

代码参考
作者:神奕的博客
然而这只是基础模板,实际算法题会在模板上更变.
一道拓扑排序题hdu2647 http://acm.hdu.edu.cn/showproblem.php?pid=2647
可以用模板练练手.