一個較大的工程往往被劃分成許多子工程,我們把這些子工程稱作活動(activity)。在整個工程中,有些子工程(活動)必須在其它有關子工程完成之後才能開始,也就是說,一個子工程的開始是以它的所有前序子工程的結束為先決條件的,但有些子工程沒有先決條件,可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先後關係,可用一個有向圖來表示,圖中的頂點代表活動(子工程),圖中的有向邊代表活動的先後關係,即有向邊的起點的活動是終點活動的前序活動,只有當起點活動完成之後,其終點活動才能進行。通常,我們把這種頂點表示活動、邊表示活動間先後關係的有向圖稱做頂點活動網(Activity On Vertex network),簡稱AOV網。
program TopSort;varmap,link:array[1..100,1..100]ofinteger;v,pnt:array[1..100]ofinteger;n,m,a,b,i,j,k:integer;beginfillchar(map,sizeof(map),0);fillchar(link,sizeof(link),0);fillchar(v,sizeof(v),0); //初始化readln(n,m);for i:=1 to m do begin //讀圖readln(a,b);map[a,b]:=1;v[b]:=v[b]+1;end;i:=0;link:=map;while (i<n) do begin //開始排序 j:=1;while (v[j]<>0) do inc(j);v[j]:=-1;for k:=1 to n do if link[j,k]=1 then begindec(v[k]);link[j,k]:=0;end;inc(i);pnt[i]:=j;end;fori:=1 to n doln(pnt[i]);end.
program topsort;typenode=^link;link=recordprocedure addd(x,y:longint);var p:node;beginnew(p);p^.g:=y;p^.next:=nd[x];nd[x]:=p;inc(ru[y]);end;beginreadln(n,m);for a:=1 to m dobeginreadln(x,y);addd(x,y);end;for a:=1 to n doif ru[a]=0 then begininc(stk);stack[stk]:=a;end;be:=0;repeatinc(be);x:=stack[be];p:=nd[x];write(x,'');while p<>nil dobegindec(ru[p^.g]);if ru[p^.g]=0 then begininc(stk);stack[stk]:=p^.g;end;p:=p^.next;end;until be=stk;readln;end.