如果我们有一组任务完成，而有些任务人才的其他任务结束后开始。因此，我们必须非常小心，这些任务的运行顺序。

假设这些任务很简单的字的运行顺序，我们可以用它们来存储列表，这是一个非常好的方案，这样我们就可以知道运行秩序完全任务。

间的关系是非常复杂的。有些任务依赖于两个甚至很多其它的任务，或者反过来非常多任务依赖自己。

因此我们不能通过链表或者树的数据结构来对这个问题建模。对这类问题唯一合理的数据结构就是图。我们须要哪种图呢？非常显然，我们须要有向图来描写叙述这样的关系，并且是不能循环的有向图，我们称之为有向无环图。要通过拓扑排序对图形进行排序，这些图必须是不能循环和有向的。

为什么这些图不能循环呢？答案非常明显，假设图形是循环的。我们无法知道哪个任务该优先运行，也不可能对任务进行排序。如今我们一要做的是对图中的每一个节点排序。组成一条条边（u。v）。u在v之前运行。

然后我们就能够得到全部任务的线性顺序。并按这样的顺序运行任务就一切都OK了。

比如,以下的图的一个拓扑排序是“5 4 2 3 1 0”。一个图能够有多个拓扑排序。

还有一个拓扑排序是“4 5 2 3 1 0”。拓扑排序的第一个顶点总是入度为0。

方法一

如今我们能够得到这个算法的基本步骤：

1.构造空列表 L和S；2.把全部没有依赖节点(入度为0)的节点放入L；3.当L还有节点的时候，运行以下步骤：3.1     L中拿出一个节点ｎ（从L中remove掉），并放入S3.2         对每个邻近n的节点m，3.2.1           去掉边（n,m）;（表示增加终于结果集S）3.2.2           假设m没有依赖节点（入度为零），把m放入L;

核心就是：每次都选取入度为0的节点，再更新其相邻的节点的入度 。

这个是相对照较直观的算法，也是常见的一种算法。我们用一个数组degree[]记录全部顶点的入度。

删除点时更新该数组。

參考以下代码函数：topologicalSort1()

方法二

第二种方法是參考DFS，对图的深度优先遍历做些改动。

我们确信在有向图中假设存在一条边（u，v），那么顶点u会先于顶点v进入列表中。因此在深度遍历时，用栈来存储遍历的顺序。參考以下代码的函数：topologicalSort2()

C++实现

// C++实现的拓扑排序算法#include
     
      #include 
      
       #include 
       
        using namespace std;// 图类class Graph{    int V;    //顶点个数    // 邻接表    list
        
          *adj;    // 拓扑排序方法 2的辅助函数    void topologicalSortRecall(int v, bool visited[], stack
         
           &Stack);public:    Graph(int V);     // 加入边    void addEdge(int v, int w);    //拓扑排序普通方法    void topologicalSort1();    // 拓扑排序方法二    void topologicalSort2();};Graph::Graph(int V){    this->V = V;    adj = new list
          
           [V];}void Graph::addEdge(int v, int w){ adj[v].push_back(w); //}//相似深度优先遍历。将和V相邻的顶点（且为訪问过的）放入栈中void Graph::topologicalSortRecall(int v, bool visited[], stack
           
             &stk){ //标记v为訪问过的 visited[v] = true; // 对每一个顶点进行递归调用 list
            
             ::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSortRecall(*i, visited, stk); // 保存顶点 stk.push(v);}// 方法二，使用递归调用实现拓扑排序void Graph::topologicalSort2(){ stack
             
               stk; bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; //每一个顶点都调用一次 for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortRecall(i, visited, stk); // 打印 while (stk.empty() == false) { cout << stk.top() << " "; stk.pop(); }}// 方法一void Graph::topologicalSort1(){ list
              
               ::iterator j; int degree[V]; //遍历全部的边，计算入度 for(int i=0; i
               

zeroNodes;//全部入度为0的点 list

result;//全部入度为0的点 for(int i=0; i

0){ int top = zeroNodes.back(); zeroNodes.pop_back(); result.push_back(top); for (j = adj[top].begin(); j != adj[top].end(); ++j){ degree[*j]--;//删除和top相邻的边，并更新其他顶点的入度 if(degree[*j] == 0) zeroNodes.push_back(*j); } } //打印结果 for(j= result.begin(); j != result.end(); j++) cout << (*j) << " ";}int main(){ // 创建文中所以的图 Graph g(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); cout << "Following is a Topological Sort of the given graph using topologicalSort1\n"; g.topologicalSort1(); cout << endl; cout << "Following is a Topological Sort of the given graph using topologicalSort2\n"; g.topologicalSort2(); return 0;}

参考：http://www.geeksforgeeks.org/topological-sorting/