1.拓扑排序的定义
拓扑排序是对有向无环图的顶点的一种排序，每个顶点只出现一次，如果存在一条从顶点A到顶点B的路径，那么在排序中出现在A的后面。
拓扑排序是利用图中的偏序关系，得到图的全序关系。
离散数学中的偏序定义是：
偏序是集合S上的二元关系R,它具有自反性，反对称性和传递性。即对S中的元素a,b,有
(1) aRa (自反性)
(2) aRb,bRa,则a=b (反对称性)
(3) aRb,且bRc则aRc (传递性)
带有偏序的集合称为偏序集合。例如实数集合中的小于等于的关系就是一种偏序关系，因为任取实数a,b有a<=a(自反性), a<=b,b<=a,则a=b(反对称性)，a<=b,b<=c,则a<=c(传递性)。
全序指的是在集合S中，任意两个元素a,b都有aRb或者bRa。全序也是一种偏序。
2. 拓扑排序的算法
(1)查找图中入度为零的顶点，放入栈中
(2)当栈不为空时，从栈中弹出一个顶点，并且输出它，遍历它的所有邻接顶点，将这些顶点的入度减去1。
(3)重复（1），（2），直到图中不存在入度为零的顶点
3. 拓扑排序示例
拓扑排序的结果为 A B E C D
4.拓扑排序的时间复杂度分析
对于有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度是O(e),建零入度顶点栈的时间复杂度为O(n)，在拓扑的排序中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减去1的操作在循环语句里面执行e次，所以，总的时间复杂度是O(n+e).
5.拓扑排序的代码
# include <iostream>
using namespace std;
# include <stdlib.h>
# include <stack>
# define NUM 10
int indegree[NUM]={0};
stack <int> s;
struct anode{
int data;
anode *next;
};
struct bnode{
char name;
anode *next;
};
struct graph{
int num;
int arc;
bnode arr[NUM];
};
int main()
{
void print(graph &g);
void create(graph &g);
void topsort(graph &g);
graph g;
create(g);
print(g);
topsort(g);
system("pause");
return 0;
}
int locate(graph &g,char a)
{
int i=0;
for(;i<g.num;i++)
{
if (g.arr[i].name==a)
return i;
}
return -1;
}
void create(graph &g) //创建图的邻接链表表示
{
cout<<"input the num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
int i=0;
for(;i<g.num;i++)
{
cout<<"input the names of node"<<endl;
cin>>g.arr[i].name;
g.arr[i].next=NULL;
}
for(i=0;i<g.arc;i++)
{
char a,b;
cout<<"input node a and node b"<<endl;
cin>>a>>b;
int i=locate(g,a);
int j=locate(g,b);
anode *p=new anode;
p->data=j;
p->next=g.arr[i].next;
g.arr[i].next=p;
}
}
void print(graph &g) //打印图的结点
{
int i=0;
while(g.arr[i].next!=NULL&&i<NUM)
{
cout<<g.arr[i].name<<":";
anode *e=g.arr[i].next;
while(e)
{
cout<<e->data;
e=e->next;
}
i++;
cout<<endl;
}
}
void topsort(graph &g) //拓扑排序
{
int count=0;
int i,t;
anode *p=new anode;
for(i=0;i<g.num;i++) //计算各个顶点的入度
{
p=g.arr[i].next;
while(p)
{
indegree[p->data]++;
p=p->next;
}
}
for(i=0;i<g.num;i++) //把所有入度为零的顶点入栈
{
if (indegree[i]==0)
s.push(i);
}
while(!s.empty())
{
t=s.top();
s.pop();
cout<<t<<endl; //弹出栈顶元素并且打印它
count++;
p=g.arr[t].next;
while(p)
{
indegree[p->data]--;
if(indegree[p->data]==0) //寻找入度为零的顶点，把它入栈
s.push(p->data);
p=p->next;
}
}
if(count<g.num) //如果计数小于图中的结点数目，说明图中有环
cout<<"has a loop"<<endl;
}
原文：http://blog.csdn.net/u011608357/article/details/21323995