拓扑排序

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

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

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

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

 

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

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

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

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

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

                                                       

3.拓扑排序的复杂度：

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

 

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

#include <iostream>
#include <list>
#include <queue>
#include<vector>
using namespace std;

class Graph
{
public:
    Graph(int v);
    ~Graph();
    bool TopoSort(vector<int> &sort_list);
    void AddEdge(int v, int w);
private:
    int VertexNum;                       //顶点个数
    list<int> *Adjlist;                  //图的邻接链表
    queue<int> NonInputVertex;           //入度为0的顶点
    vector<int> VertexInputNum;          //每个顶点的入度个数
};

Graph::Graph(int v)
{
    this->VertexNum = v;
    this->Adjlist = new list<int>[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<int> &sort_list)
{
    for(int i=0; i<VertexNum; i++)
    {
        if(VertexInputNum[i] == 0)
            NonInputVertex.push(i);    //统计入度为0的顶点，将其加入队列
    }
    int cnt = 0;
    while( ! NonInputVertex.empty())
    {
        cnt++;
        int ver = NonInputVertex.front();
        NonInputVertex.pop();
        sort_list.push_back(ver);        //将队列出队顺序记录，即为topo排序的结果
        for(auto iter = Adjlist[ver].begin(); iter!= Adjlist[ver].end(); ++iter)    //将出队顶点相连的输出边删除，将输出边相连的入度为0的顶点入队
        {
            if( 0 == (--VertexInputNum[*iter]) )
                NonInputVertex.push(*iter);
        }
    }
    if(cnt == VertexNum)
        return true;
    else                             //顶点没有全部删除，说明图不是无环图，topo排序无解。
        return false;
}