引例
以一个例子开始引进拓扑排序： 
根据这个表，我们可以每个课程表示为图的顶点，<V,W>表示边，V为W的预修课程，画出图：
这样就构成了一个 AOV网络，即Activity On Vertex 网络。
给每个学期排课，根据这个图排成的序列成为拓扑序：
拓扑排序
- 如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序
- 获得一个拓扑序的过程就是拓扑排序
- AOV如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph，DAG）
算法伪代码
void TopSort() { for(each vertex V in the graph) { if(Indegree[V] == 0) //这里把所有入度为0的顶点入队 Enqueue(V, Q); } while(!IsEmpty(Q)) { V = Dequeue(Q); //从队列中取出顶点，该顶点的入度一定为0 输出(V); // 输出V，或者记录V的输出序号 cnt++; //记录输出的顶点的个数，用于判断图中是否有回路 for(each adjacent vertex W of V) //把V的所有邻接点的入度都减1 { if(--Indegree[W] == 0) Enqueue(W, Q); } } if(cnt != number of vertices in the graph) //判断输出顶点的个数（即入度为0的顶点个数）是否与图中的顶点数量相等，如果不相等，则说明图中有回路 Error("The graph contains a cycle"); }
时间复杂度
稀疏图： 
稠密图： 
此算法可以用来检测有向图是否DAG。
代码（C语言）
/* 邻接表存储 - 拓扑排序算法 */ bool TopSort( LGraph Graph, Vertex TopOrder[] ) { /* 对Graph进行拓扑排序, TopOrder[]顺序存储排序后的顶点下标 */ int Indegree[MaxVertexNum], cnt; Vertex V; PtrToAdjVNode W; Queue Q = CreateQueue( Graph->Nv ); /* 初始化Indegree[] */ for (V=0; V<Graph->Nv; V++) Indegree[V] = 0; /* 遍历图，得到Indegree[] */ for (V=0; V<Graph->Nv; V++) for (W=Graph->G[V].FirstEdge; W; W=W->Next) Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */ /* 将所有入度为0的顶点入列 */ for (V=0; V<Graph->Nv; V++) if ( Indegree[V]==0 ) AddQ(Q, V); /* 下面进入拓扑排序 */ cnt = 0; while( !IsEmpty(Q) ){ V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */ TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */ /* 对V的每个邻接点W->AdjV */ for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */ AddQ(Q, W->AdjV); /* 则该顶点入列 */ } /* while结束*/ if ( cnt != Graph->Nv ) return false; /* 说明图中有回路, 返回不成功标志 */ else return true; }
关键路径问题
关键路径问题是拓扑排序的一个应用，用到了另外一种网络。
AOE（Activity On Edge）网络，一般用于安排项目的工序。
关键路径：由绝对不允许延误的活动组成的路径。
以下就是一个比较典型的AOE网络图：
画出了这个图，我们就可以知道：
- 整个工程的工期为18（Earliest[ 8 ] = 18）
- 哪个组有机动时间（D<i，j> = Latest[ j ] - Earliest[ i ] - C<i,j>）
