拓扑排序73934.docVIP

3.1AOV网 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。如下图是计算机专业课程之间的先后关系： 3. 2 拓扑排序 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。如上图的拓扑排序基础知识；Pascal；数据结构；离散数学。或 基础知识；离散数学Pascal；数据结构。 拓扑排序的方法和步骤： （1）在图中选一个没有前趋的顶点并输出之 （2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。 若图中存在回路，拓扑排序无法进行。 以下是将一AOV网进行拓扑排序的算法： 网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。 （1）计算各顶点的入度（2）找入度为零的点输出之，删除该点该点与该点关联各点的入度减1 （3）若所有顶点都输出完毕若存在回路。 程序如下： program tppv; const maxn=100; var ?map:array[1..maxn,1..maxn] of byte; ?into:array[1..maxn] of byte; ?n,i,j,k:byte; procedure init; var ?i,j:integer; begin ?read(n); ?for i:=1 to n do ? for j:=1 to n do ?? begin ?? read(map[i,j]); ?? inc(into[j]); ?? end; end; begin ?init; ?for i:=1 to n do ? begin ?? j:=1; ?? while (j=n)and(into[j]0) do inc(j); ?? write(j, ); ?? into[j]:=255; ?? for k:=1 to n do ??? if map[j,k]=1 then dec(into[k]); ? end; end. 3.３应用举例与练习? 例：士兵排队问题： 有N个士兵（1=N=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比2 高，7 比 5高”这样的比较结果。 输入文件：第一行为数N（N〈=100）；表示士兵的个数。以下若干行每行两个数A，B??? 表示A高于B。 输出文件：给出一个合法的排队序列。 程序如下： program tppv; const maxn=100; var ?map:array[1..maxn,1..maxn] of byte; ?into:array[1..maxn] of byte; ?n,i,j,k:byte; ?fp:text; procedure init; var ?i,j:integer; begin ?assign(fp,tp.txt); ?reset(fp); ?readln(fp,n); ?fillchar(map,sizeof(map),0); ?fillchar(into,sizeof(into),0); ?while not(seekeof(fp)) do ?? begin ?? readln(fp,i,j); ?? map[i,j]=1 ; ?? inc(into[j]); ?? end; ? close(fp); end; begin ?init; ?for i:=1 to n do ? begin ?? j:=1; ?? while (j=n)and(into[j]0) do inc(j); ?? write(j, ); ?? into[j]:=255; ?? for k:=1 to n do ??? if map[j,k]=1 then dec(into[k]); ? end; end. 　 4.1 AOE网 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网,如下图。 　 　 AOE网具有以下性质： （1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 （2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。 可以将上图假想一个工程有6项活动，网中5个顶点，分别表示