1. 拓扑排序的先决条件：

         图必须是一个无环有向图。序列必须满足的条件：

　　　　（1）每个顶点出现且只出现一次。

　　　　（2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

 

2.拓扑排序的思想（源删除算法）：

   （1）选择一个没有输入边（入度为0）的源顶点（若有多个则任选一个），将它和它的输出边删除。

   （2）重复源顶点的删除操作，直到不存在入度为0的源顶点为止。

   （3）最终，检测图中的顶点个数，若还有顶点存在则算法无解，否则顶点的删除顺序就是拓扑排序的输出顺序。

              

 （ps：算法无解表示整个图不是无环图）

                                                       

3.拓扑排序的复杂度：

       由于删除顶点的同时还要删除它的输出边，所以拓扑排序的时间复杂度是： O(V+E)

 

4.拓扑排序的C++程序：

#include 
      
       #include 
       
        #include 
        
         #include
         
          using namespace std;class Graph{public:    Graph(int v);    ~Graph();    bool TopoSort(vector
          
            &sort_list);    void AddEdge(int v, int w);private:    int VertexNum;                       //顶点个数    list
           
             *Adjlist; //图的邻接链表 queue
            
              NonInputVertex; //入度为0的顶点 vector
             
               VertexInputNum; //每个顶点的入度个数};Graph::Graph(int v){ this->VertexNum = v; this->Adjlist = new list
              
               [v]; this->VertexInputNum.resize(v);}Graph::~Graph(){ delete [] Adjlist;}void Graph::AddEdge(int v, int w){ this->Adjlist[v].push_back(w); VertexInputNum[w]++; // w的入度值增加}bool Graph::TopoSort(vector
               
                 &sort_list){ for(int i=0; i