6.6 拓 扑 排 序
6.6 拓 扑 排 序
在谈到拓扑排序前，先来讨论几个名词。
· AOV-network：在一个有向图中，每一个顶点代表工作（Task）或活动（Activity），而边表示工作之间的优先级（Precedence Relations），即边（Vi, Vj）表示Vi的工作必先处理完后才能去处理Vj的工作，这种有向图称为顶点表示活动的网（Activity on Vertex network）或AOV-网（AOV-network）。
· 直接前驱（Immediate Predecessor）与直接后继（Immediate Successor）：若在有向图G中，有一边< Vi, Vj >，则称Vi是Vj的直接前驱，而Vj是Vi的直接后继。在图6-25中V7是V8、V9、V10的直接前驱，而V8、V9、V10是V7的直接后继。
· 前驱（Predecessor）与后继（Successor）：在AOV-network中，假若从顶点Vi到顶点Vj存在一条路径，则称Vi是Vj的前驱，而Vj是Vi的后继。如图6-25中V3是V6的前驱，而V6是V3的后继。
图6-25 AOV-网示意图
若在AOV-network中，Vi是Vj的前驱，则在线性排列中Vi一定在Vj的前面，此种特性称为拓扑排序（Topological Sort）。如何寻找AOV-network的拓扑排序呢？其过程如下：
（1）在AOV-network中任意挑选没有前驱的顶点。
（2）输出此顶点，并将此顶点所连接的边删除。重复（1）及（2），一直到全部的顶点都输出为止。
下面以图6-26为例来说明其拓扑排序过程。
图6-26 拓扑排序实例示意图
①输出V1，并删除<V1,V2>与<V1,V6>两个边，如图6-27所示。
图6-27 执行第①步后的AOV-网示意图
②此时V2和V6都没有前驱，若输出V2则删除<V2,V3>与<V2,V4>两个边，如图6-28所示。
图6-28 执行第②步后的AOV-网示意图
③ 运用相同的原理，选择输出V6，并删除<V6,V4>与<V6,V5>两个边，如图6-29所示。
④输出V3，并删除<V3,V5>与<V3,V7>两个边，如图6-30所示。
图6-29 执行第③步后的AOV-网示意图 图6-30 执行第④步后的AOV-网示意图
⑤输出V4，并删除<V4,V5>，如图6-31所示。
⑥输出V5，并删除<V5,V8>，如图6-32所示。
图6-31 执行第⑤步后的AOV-网示意图 图6-32 执行第⑥步后的AOV-网示意图
⑦输出V7，并删除<V7,V8>，如图6-33所示。
图6-33 执行第⑦步后的AOV-网示意图
⑧输出V8。
图6-26的拓扑排序并非只有一种，因为在第②步时，假如选的顶点不是2，其拓扑排序所排出来的顺序就会不一样，因此AOV-network的拓扑排序并不唯一。若依上述方式，其数据的排列顺序是V1，V2，V6，V3，V4，V5，V7及V8。
为了实现拓扑排序的算法，对于给定的有向图，采用邻接表作为存储结构，为每个顶点设立一个链表，每个链表有一个表头节点，这些表头节点构成一个数组，表头节点中增加一个存放顶点入度的域count。即将邻接表定义中的VNode类型修改如下：
typedef struct /*表头节点类型*/
{
Vertex data; /*顶点信息*/
int count; /*存放顶点入度*/
ArcNode *firstarc; /*指向第一条弧*/
} VNode;
在执行拓扑排序的过程中，当某个顶点的入度为零（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为零的顶点，设立一个栈St，以存放入度为零的顶点。执行拓扑排序的算法如下：
void TopSort(VNode adj[],int n)
{
int i,j;
int St[MAXV],top=-1; /*栈St的指针为top*/
ArcNode *p;
for(i=0;i<n;i++)
if(adj[i].count==0) /*入度为0的顶点入栈*/
{
top++;
St[top]=i;
}
while (top>-1) /*栈不为空时循环*/
{
i=St[top];top--; /*出栈*/
printf("%d ",i); /*输出顶点*/
p=adj[i].firstarc; /*找第一个相邻顶点*/
while(p!=NULL)
{
j=p->adjvex;
adj[j].count--;
if(adj[j].count==0) /*入度为0的相邻顶点入栈*/
{
top++;
St[top]=j;
}
p=p->nextarc; /*找下一个相邻顶点*/
}
}
}
【例6-2】给出图6-34所示的有向图G8的全部可能的拓扑排序序列。
图6-34 有向图G8
解：从图G8中看到，入度为0有两个顶点，即0和4。
先考虑顶点0，删除顶点0及相关边，入度为0的有顶点4；删除顶点4及相关边，入度为0的有顶点1和顶点5；考虑顶点1，删除顶点1及相关边，入度为0的有顶点2和顶点5；如此得到拓扑序列：041253，041523，045123。再考察顶点4，类似地得到拓扑序列：450123，401253，405123，401523。