描述：
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 ∈E(G)，则u在线性序列中出现在v之前。
一般应用：
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
实现的基本方法：
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
代码：
（1）邻接矩阵实现
#include<iostream>
#include<cstdlib>
using namespace std;
class Graph{
friend istream& operator>>(istream& in,Graph& g)
{
int vstart,vend;
cout<<"Input the vertices:"<<endl;
for(int i=0;i<g.numEdges;i++){
in>>vstart>>vend;
g.edge[vstart][vend] = 1;
}
return in;
}
friend ostream& operator<<(ostream& out,const Graph& g)
{
out<<"numEdges:"<<g.numEdges<<",numVertices:"<<g.numVertices<<endl;
for(int i=0;i<g.numVertices;i++){
for(int j=0;j<g.numVertices;j++){
cout<<g.edge[i][j]<<" ";
}
cout<<endl;
}
return out;
}
public:
Graph(int numEdges,int numVertices)
{
this->numEdges = numEdges;
this->numVertices = numVertices;
edge = (int **)new int*[numVertices];
for(int i=0;i<numVertices;i++){
edge[i] = new int[numVertices];
/*memset(edge[i],0,numVertices);*/
for(int j=0;j<numVertices;j++)
edge[i][j] = 0;
}
}
int findZeroNode(int v[])
{
int count;
int i,j;
for(i=0;i<numVertices;i++){
if(v[i]!=0)continue;
count = 0;
for(j=0;j<numVertices;j++){
if(edge[j][i]!=0)count++;
}
if(count==0)break;
}
if(i!=numVertices)return i;
else return -1;
}
void topsort()
{
cout << "The topsort:" <<endl;
int i,j;
int *visited = new int[numVertices];
for(i=0;i<numVertices;i++)visited[i] = 0;
for(i=0;i<numVertices;i++){
int v = findZeroNode(visited);
visited[v] = 1;
if (v==-1){
cout << "The graph has cycle, can not do topsort"<<endl;
return;
}
cout<<v<<" ";
for(j=0;j<numVertices;j++){//因为v是入度为0的点，所以删除v的出度的点就行了
edge[v][j] = 0;
}
}
cout<<endl;
delete[] visited;
};
~Graph()
{
for(int i=0;i<numVertices;i++){
delete[] edge[i];
}
delete[] edge;
}
private:
int numEdges;//边数
int numVertices;//顶点个数
int **edge;//邻接矩阵
};
int main()
{
Graph g(12,7);
cin>>g;
cout<<g<<endl;
g.topsort();
system("pause");
}
（2）邻接表实现
#include<iostream>
using namespace std;
#define MAX_VERTEX 10
struct edge{//边列表
int nodeNum;//边的终点
edge* link;
edge(int node,edge*l = NULL):nodeNum(node),link(l){}
};
struct vertexNode //顶点列表
{
edge *list;//顶点所接的边
int indegree;//入度
vertexNode():list(NULL),indegree(0){}
};
class Graph{
friend ostream& operator<<(ostream& out,const Graph& g)
{
out << "The adjacent list for graph is:" << endl;
for(int i=0;i<g.numVertices;i++){
out<<i<<"(indegree = "<<g.nodeTable[i].indegree<<")"<<"->";
edge* tmp = g.nodeTable[i].list;
while(tmp){
out<<tmp->nodeNum<<" ";
tmp = tmp->link;
}
out<<endl;
}
return out;
}
friend istream& operator>>(istream& in,Graph& g)
{
int i,edgeStart,edgeEnd;
for (i=0;i<g.numEdges; i++)
{
in>>edgeStart>>edgeEnd;
edge* node = new edge(edgeEnd,g.nodeTable[edgeStart].list);
g.nodeTable[edgeStart].list = node;
g.nodeTable[edgeEnd].indegree++;
}
return in;
}
public:
Graph(int numEdges,int numVertices = MAX_VERTEX)
{
this->numEdges = numEdges;//边数
this->numVertices = numVertices;//顶点个数
nodeTable = new vertexNode[numVertices];//存储各个顶点的相邻接点
}
int findZeroNode(int v[])
{
int i;
for(i=0;i<numVertices;i++){
if(v[i]==1)continue;//已被访问过
if(nodeTable[i].indegree==0)break;
}
if(i==numVertices)return -1;
else return i;
};
void topSort()
{
int i;
int *visited = new int[numVertices];
for(i=0;i<numVertices;i++)visited[i] = 0;
cout<<"The topsort:"<<endl;
for(i=0;i<numVertices;i++){
int v = findZeroNode(visited);//找入度为0的点
if(v==-1){
cout << "The graph has cycle, can not do topsort"<<endl;
return;
}
visited[v] = 1;//标记被访问
cout<<v<<" ";
nodeTable[v].indegree = 0;
edge *node = nodeTable[v].list;//删除以v为起点的边，即从图中删除v点
while(node){
nodeTable[node->nodeNum].indegree--;
node = node->link;
}
}
delete[] visited;
};
~Graph(){
int i;
for(i=0;i<numVertices;++i){
edge *tmp = NULL;
while(nodeTable[i].list!=NULL){
tmp = nodeTable[i].list;
nodeTable[i].list = nodeTable[i].list->link;
delete tmp;
tmp = NULL;
}
}
}
private:
int numVertices;
int numEdges;
vertexNode *nodeTable;
};
int main()
{
Graph g(12,7);
cin>>g;
cout<<g;
g.topSort();
system("pause");
return 0;
}