一、什么是拓扑排序
拓扑排序是对有向无圈图的顶点的一种排序，它使得如果存在一条从 \(v_{i}\) 到 \(v_{j}\) 的路径，那么排序中 \(v_{j}\) 出现在 \(v_{j}\) 的后面。有向边 (v,w) 表明任务 v 必须在任务 w 前完成。显然，如果图含有圈，那么拓扑排序是不可能的，因为对于圈上的两个顶点 v 和 w，v 先于 w 同时 w 又先于 v。此外排序不是唯一的，任何合理的排序都是可以的。
二、拓扑排序的实现
一个简单的求拓扑排序的算法是先找到任意一个没有进入边的顶点。然后我们显印出该顶点，并将它和它的边一起从图中删除。然后，我们对图的其余部分同样应用这样的方法处理。
/**
* @brief 拓扑排序
*
* @param graph 待操作的图
*/
void TopSort(Graph graph)
{
int counter = 0;
int v = 0,w = 0;
int topNum[graph->vertexNum];
int indegree[graph->vertexNum]; //创建记录各顶点入度的数组
FindIndegree(graph,indegree); //统计各顶点的入度
// 图中的每一个顶点
for(counter = 0; counter < graph->vertexNum; counter++)
{
// 未输出入度为0的顶点
v = FindNewVertexOfIndegreeZero(indegree,graph->vertexNum); // 查找入度为0的顶点
// 如果这样的v不存在
if(v == -1)
{
printf("图存在回路！\n");
break;
}
//输出v，或记录v的输出序号
topNum[v] = counter;
printf("%-5c",graph->vertex[v]);
// v的每个邻接点w
for(w = GetFirstNeighbor(graph,v); w >= 0; w = GetNextNeighbor(graph,v,w))
{
indegree[w]--;
}
}
}
/**
* @brief 获取图中各结点的入度
*
* @param graph 待操作的图
* @param indegree 各顶点入度的数组
*/
void FindIndegree(Graph graph,int indegree[])
{
int i = 0, j = 0;
//初始化数组，默认初始值全部为 0
for(i = 0; i < graph->vertexNum; i++)
{
indegree[i]=0;
}
//遍历邻接表，根据各链表中结点的数据域存储的各顶点位置下标，在 indegree 数组相应位置+1
for (i = 0; i < graph->vertexNum; i++)
{
for(j = 0; j < graph->vertexNum; j++)
{
if(graph->edge[j][i] != 0)
{
indegree[i]++;
}
}
}
}
/**
* @brief 查找入度为0的顶点
*
* @param indegree 各顶点入度的数组
* @param N 数组的大小
* @return int 如果找到则返回对应顶点的下标，否则返回-1
*/
int FindNewVertexOfIndegreeZero(int indegree[],int N)
{
int i = 0;
for(i = 0; i < N; i++)
{
if(indegree[i] == 0)
{
indegree[i]--;
return i;
}
}
return -1;
}
因为 FindNewVertexOfIndegreeZero 是对 Indegree 数组的一个简单的顺序扫描，所以每次对它的调用都花费 \(O(|v|)\) 时间。由于 \(|V|\) 次这样的调用，因此该算法的时间复杂度为：\(T = O(V^{2})\)。
为了提高程序的运行效率，我们可以随时将入度为 0 的顶点放在一个容器中。首先，对每一个顶点计算它的入度。然后，将所有入度为 0 的顶点放入一个初始为空的队列中。当队列不空时，并将与 v 邻接的所有的顶点的入度减 1。只要一个顶点的入度降为 0，就把该顶点放入队列中。此时，拓扑排序就是顶点出队的顺序。
/**
* @brief 拓扑排序
*
* @param graph 待操作的图
*/
void TopSort(Graph graph)
{
int counter = 0;
int v = 0,w = 0;
int topNum[graph->vertexNum];
int indegree[graph->vertexNum]; //创建记录各顶点入度的数组
FindIndegree(graph,indegree); //统计各顶点的入度
Queue Q = CreateQueue();
// 图中的每一个顶点v
for(v = 0; v < graph->vertexNum; v++)
{
if(indegree[v] == 0)
{
Enqueue(Q,v);
}
}
while(!QueueIsEmpty(Q))
{
// 输出V，或者记录V的输出序号;
v = Dequeue(Q);
printf("%-5c",graph->vertex[v]);
topNum[v] = ++counter;
// v的每个邻接点w
for(w = GetFirstNeighbor(graph,v); w >= 0; w = GetNextNeighbor(graph,v,w))
{
if(--indegree[w] == 0) // w为v尚未访问的邻接顶点
{
Enqueue(Q,w);
}
}
}
if(counter != graph->vertexNum)
{
printf("图存在回路！\n");
}
}
如果使用邻接表，那么执行这个算法所用的时间复杂度为：\(T = O(|V| + |E|)\)。
三、逆拓扑排序
对于一个 AOV 网，如果采用下列步骤进行排序，则称之为 逆拓扑排序：
- 从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出；
- 从网中删除该顶点和所有以它为终点的有向边；
- 重复 ① 和 ② 直到当前的 AOV 网为空；