拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。假设有环，则无法表示两个顶点的先后顺序。
在现实生活中，也会有不少应用样例，比方学校课程布置图，要先修完一些基础课，才干够继续修专业课。
一个简单的求拓扑排序的算法：首先要找到随意入度为0的一个顶点，删除它及全部相邻的边，再找入度为0的顶点，以此类推，直到删除全部顶点。顶点的删除顺序即为拓扑排序。
非常easy得到拓扑排序的伪代码：
void TopSort（Graph g）
{
for (int i=0; i<vertexnum; i++)
{
vertex v = FindZeroIndegree(g);
if (v is not vertex)
cout <<"the graph has cycle"<<endl;
cout << v ;
foreach vertex w adjacent to v
w.indegree--;
}
}
相同以上图为例，对于该图进行拓扑排序会得到：v1 v2 v5 v4 v3 v7 v6 或者v1 v2 v5 v4 v7 v3 v6 。
仍然利用上一贴图的构建方法，进行验证。
代码实现：
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
struct adjVertexNode
{
int adjVertexPosition;
adjVertexNode* next;
};
struct VertexNode
{
char data[2];
adjVertexNode* list;
int indegree;
};
struct Graph
{
VertexNode VertexNode[MAX_VERTEX_NUM];
int vertexNum;
int edgeNum;
};
void CreateGraph (Graph& g)
{
int i, j, edgeStart, edgeEnd;
adjVertexNode* adjNode;
cout << "Please input vertex and edge num (vnum enum):" <<endl;
cin >> g.vertexNum >> g.edgeNum;
cout << "Please input vertex information (v1)/n note: every vertex info end with Enter" <<endl;
for (i=0;i<g.vertexNum;i++)
{
cin >> g.VertexNode[i].data; // vertex data info.
g.VertexNode[i].list = NULL;
g.VertexNode[i].indegree = 0;
}
cout << "input edge information(start end):" <<endl;
for (j=0; j<g.edgeNum; j++)
{
cin >>edgeStart >>edgeEnd;
adjNode = new adjVertexNode;
adjNode->adjVertexPosition = edgeEnd-1; // because array begin from 0, so it is j-1
adjNode->next=g.VertexNode[edgeStart-1].list;
g.VertexNode[edgeStart-1].list=adjNode;
//每添加一条边，则边的End顶点的入度加1
g.VertexNode[edgeEnd-1].indegree++;
}
}
void PrintAdjList(const Graph& g)
{
cout << "The adjacent list for graph is:" << endl;
for (int i=0; i < g.vertexNum; i++)
{
cout<< g.VertexNode[i].data << "->";
adjVertexNode* head = g.VertexNode[i].list;
if (head == NULL)
cout << "NULL";
while (head != NULL)
{
cout << head->adjVertexPosition + 1 <<" ";
head = head->next;
}
cout << endl;
}
}
VertexNode& FindZeroIndegree(Graph& g)
{
for (int i=0; i<g.vertexNum; i++)
{
if (g.VertexNode[i].indegree==0)
return g.VertexNode[i];
}
return g.VertexNode[0];
}
void TopSort(Graph& g)
{
cout << "The topsort is:" <<endl;
for (int i=0; i<g.vertexNum; i++)
{
VertexNode& v = FindZeroIndegree(g);
if (v.indegree!=NULL)
cout << "The graph has cycle, can not do topsort"<<endl;
// print graph as topsort.
cout<< v.data << " ";
// for each vertex w adjacent to v, --indegree
adjVertexNode* padjv = v.list;
while (padjv!=NULL)
{//！！这个算法这里破坏了原图中的入度信息。最后入度均为1
g.VertexNode[padjv->adjVertexPosition].indegree--;
padjv = padjv->next;
}
//避免入度信息均为零FindZeroIndegree找到删除的顶点，将删除的顶点入度置为1
v.indegree++;
}
cout << endl;
}
void DeleteGraph(Graph &g)
{
for (int i=0; i<g.vertexNum; i++)
{
adjVertexNode* tmp=NULL;
while(g.VertexNode[i].list!=NULL)
{
tmp = g.VertexNode[i].list;
g.VertexNode[i].list = g.VertexNode[i].list->next;
delete tmp;
tmp = NULL;
}
}
}
int main(int argc, const char** argv)
{
Graph g;
CreateGraph(g);
PrintAdjList(g);
TopSort(g);
DeleteGraph(g);
return 0;
}
执行结果：
从上面的代码能发现FindZeroIndegree的时间复杂度为O(|V|),TopSort的时间复杂度为O(|V|2)
原因在于，每次删除顶点，仅仅有邻接点须要调整入度，但FindZeroIndegree却是遍历了全部顶点，甚至已经删除的顶点。
更为合理的方法是将每次遍历得出的入度为0的顶点放入一个队列。
void TopSort2(Graph& g)
{
queue<VertexNode> q;
for (int i=0; i<g.vertexNum; i++)
{
if (g.VertexNode[i].indegree == 0)
q.push(g.VertexNode[i]);
}
int count = 0;
cout << "The topsort is:" <<endl;
while (!q.empty())
{
VertexNode v = q.front();
q.pop();
cout<< v.data << " ";
count++;
adjVertexNode* padjv = v.list;
while (padjv!=NULL)
{//！！这个算法这里破坏了原图中的入度信息。最后入度均为1
if (--(g.VertexNode[padjv->adjVertexPosition].indegree)==0)
q.push(g.VertexNode[padjv->adjVertexPosition]);
padjv = padjv->next;
}
}
if (count != g.vertexNum)
cout << "The graph has cycle, can not do topsort"<<endl;
}
内部的while循环最多运行|E|次，即每条边运行一次。队列对每一个顶点最多运行一次操作，所以新算法的时间复杂度为O(|E|+|V|). 优于O（|V|2）由于拓扑图边数最多有n(n-1)/2，即O（|E|+|V|）<=O(|V|2)
