第七章-拓扑排序.doc

拓扑排序
什么是拓扑排序？
简而言之，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观地看，偏序指集合中仅有部分成员之间可以比较，而全序指集合中全体成员之间均可以比较。
由偏序定义得到拓扑有序的操作便是拓扑排序。
V1
V2 V3 V1 V2 V3 V4
V4

l 这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV-网。
在AOV-网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。
例：程序的数据流程图， 死循环。
工作流程图，工程便无法进行。
如何进行拓扑排序？
1． 在有向图中选一个没有前驱的顶点并且输出之。
2． 从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。（后一种情况则说明有向图中存在环。）
已知条件：用邻接表作为有向图的存储结构，头结点结构为：
value link adjvex next

struct Gnode struct node
{ {
int value ; int value ; int adjvex;
struct Gnode *link; struct node *next;
} }

struct Gnode G[6];
(入度)
G : value link
[1] 0 4 ∧ 3 2 ∧ V1 V2
[2] 2 ∧
[3] 1 5 2 ∧ V4 V3
[4] 2 5 ∧
[5] 3 ∧ V6 V5
[6] 0 5 4 ∧

TopoSort ( G, n )
{ int I, count ;
for ( I=0; I< n; ++I )
if( G[I].value==0 ) push( s, I );
count =0;
while( 栈不空){
pop ( s, I );
printf( I ); count++;
for ( p=G[I].link; p; p=p->next )
{
k=p->adjvex; G[I].value--;
if( G[k].value==0 ) push( s, k );
}
}
if( count <n ) return –1;
return 1;
}