余辉 -
将入度为0的结点入队，删除后同时将所有相邻顶点的先决条件减一。当某个顶点的计数为0时，将它入队。这是关键思想。
一自萧关起战尘 -
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
拓扑排序(Topological Sort)
什么是拓扑序列
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。
举例
【例】对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 ⑤当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边<v3，vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即入度为零)的顶点，其抽象算法可描述为： NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有入度为0的顶点)do{ 从G中选择一个入度为0的顶点v且输出之； 从G中删去v及其所有出边； } if(输出的顶点数目<|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error("G中存在有向环，排序失败！")； } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。 注意： 无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点： 在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时，只需做出栈(队)操作即可。 拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
实现的基本方法
拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
编辑本段在计算机语言中的应用
拓扑序列 Pascal代码：
program TopSort; var map,link:array [1..100,1..100] of integer; v,pnt:array [1..100] of integer; n,m,a,b,i,j,k:integer; begin fillchar(map,sizeof(map),0); fillchar(link,sizeof(link),0); fillchar(v,sizeof(v),0); readln(n,m); for i:=1 to m do begin readln(a,b); map[a,b]:=1; v[b]:=v[b]+1; end; i:=0; link:=map; while (i<n) do begin j:=1; while (v[j]<>0) do inc(j); v[j]:=-1; for k:=1 to n do if link[j,k]=1 then begin dec(v[k]);link[j,k]:=0; end; inc(i); pnt[i]:=j; end; for i:=1 to n do writeln(pnt[i]); end.
拓扑序列 C++核心代码
bool TopologicalSort(int a[][101]) //可以完成拓扑排序则返回True { int n = a[0][0], i, j; int into[101], ans[101]; memset(into, 0, sizeof(into)); memset(ans, 0, sizeof(ans)); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (a[i][j] > 0) into[j]++; } } into[0] = 1; for (i = 1; i <= n; i++) { j = 0; while (into[j] != 0) { j++; if (j > n) return false; } ans[i] = j; into[j] = -1; for (int k = 1; k <= n; k++) { if (a[j][k] > 0) into[k]--; } } for (i = 1; i <= n; i++) { cout << ans[i] << " "; } cout << endl; return true; }
延伸 拓扑学
拓扑学是近代发展起来的一个研究连续性现象的数学分支。中文名称起源于希腊语Τοπολογία的音译。Topology原意为地貌，于19世纪中期由科学家引入，当时主要研究的是出于数学分析的需要而产生的一些几何问题。发展至今，拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量。
下面给出一个实例：
采用邻接表作为拓扑排序算法的存储结构。所设计的系统要有简单的 DOS 界面，方便用户
进行操作，完成以下功能：
（1）实现图的基本运算，如：增加边，删除边，判断边是不是存在等。
（2）实现堆栈类，要求采用链式存储结构实现。
（3）实现拓扑排序算法，要求使用（2）中定义的堆栈类存放入度为0的顶点。
（4）输出拓扑排序的结果到文本文件中保存。
（5）退出系统。
推荐答案
#define MAXV 30
#define OK 1
#define ERROR 0
typedef char VertexType;
typedef int status;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAXV ];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph G,char m);
status Creat_Graph1(ALGraph &G);
int dfs_topsort(ALGraph g,int n);//拓扑排序算法
void dfs(ALGraph g,int v,int&flag);//深度优先搜索
void Menuselect();
头文件
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include"head.h"
int visited[MAXV];
int finished[MAXV];
int dfs_topsort(ALGraph g,int n)
{
int flag=1,i;
for(i=0;i<n;i++) //置初值
{
visited[i]=0;
finished[i]=1;
}
i=0; //从编号为0的顶点开始遍历
while(flag&&i<n)
{
if(visited[i]==0)
{ i++;
dfs(g,i,flag);}
}
return flag;
}
void dfs(ALGraph g,int v,int&flag)
{
ArcNode *p;
printf("%d ",v);
finished[v]=0;
visited[v]=0;
p=g.vertices[v]. firstarc; //找顶点V的第一条弧
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
dfs(g,p->adjvex,flag);
finished[p->adjvex ]=1;
}
p=p->nextarc ;
}
}
int LocateVex(ALGraph G,char m){
int i;
for(i=0;i<G.vexnum;i++)
if(G.vertices[i].data==m)return i;
return ERROR;
}
status Creat_Graph1(ALGraph &G){
int i,j,r;char m,n;ArcNode *p;
printf("请输入顶点数：");
scanf("%d",&G.vexnum);
printf("请输入边数：");
scanf("%d",&G.arcnum);
printf("请输入图的所有顶点：");
for(i=0;i<G.vexnum;i++)
{cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}
printf("请输入图的所有边，如A->B边记为AB，： ");
for(r=0;r<G.arcnum;r++){
cin>>m;cin>>n;
i=LocateVex(G,m);j=LocateVex(G,n);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
return OK;
}
void Menuselect(){
int done=1,select,i;
ALGraph g;
printf("please input select number");
while(done){
printf("请输入操作码：");
scanf("%d",&select);
switch(select){
case 1:
if(Creat_Graph1(g))printf("OK");
printf(" ");
break;
case 2:
dfs_topsort( g,g.vexnum);
printf(" ");
break;
case 3:
done=0;
break;
default:printf("输入的操作码错误 ");
}
}
}
实现文件
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include"head.h"
void main()
{
printf("图的拓扑排序");
Menuselect();
}
主文件