拓?fù)渑判?、關(guān)鍵路徑分析

1、1、拓?fù)渑判虻乃惴ňW(wǎng)采用鄰接矩陣 map 表示 ,若 mapi， j=1 ，表示活動(dòng) i 先于 j ，mapi，j=0 ，表示活動(dòng) i 與 j 不存在先后關(guān)系。（1）計(jì)算各頂點(diǎn)的入度into(j);（2）找入度為零的點(diǎn)輸出之，刪除該點(diǎn)，且與該點(diǎn)關(guān)聯(lián)各點(diǎn)的入度減1；（ 3）若所有頂點(diǎn)都輸出完畢。program topysort; const maxn=100; varmap:array1.maxn,1.maxn of byte; /存儲各點(diǎn)之間關(guān)系的鄰接矩陣into:array1.maxn of byte; / 各點(diǎn)的入度數(shù)量 n,i,j,k:byte; procedure init; / 輸入

2、過程 var i,j:integer; beginassign(input,'topsort.in');reset(input);assign(output,'topsort.out');rewrite(output); read(n); /讀入頂點(diǎn)數(shù)量 for i:=1 to n dofor j:=1 to n do beginread(mapi,j); / 讀入鄰接矩陣（ i,j 關(guān)系）if mapi,j=1 then inc(intoj); / j 入度為 1 則 j 點(diǎn)入度數(shù)量 intoj 累加 1 end; begin init; / 讀入數(shù)據(jù)并初始化

3、 for i:=1 to n do begin j:=1;while (j<=n)and(intoj<>0) do inc(j); /查找第一個(gè)入度為0 的點(diǎn) j write(j,' '); / 輸出jintoj:=255; / 入度不再為 0，而是 255，作為已經(jīng)輸出標(biāo)志for k:=1 to n doif mapj,k=1 then dec(intok); / 把所有以 j 為前驅(qū)的點(diǎn)的入度減去1，即刪除這條邊 end;close(output); 第 1 頁 共 4 頁2、關(guān)鍵路徑的算法program gjlj; const maxn=10; varm

4、ap:array1.maxn,1.maxn of integer; /記錄鄰接矩陣 a:array1.maxn of 0.maxn; /記錄拓?fù)渑判蚝蟮木幪朾:array1.maxn of integer; /bi 表示起點(diǎn)到 i 點(diǎn)的最長距離 c:array1.maxn of 0.maxn; /ci 表示點(diǎn) i 的前一個(gè)編號 n:integer;procedure init; var i,j:integer; beginreadln(n);for i:=1 to n do for j:=1 to n doread(mapi,j); / 讀入鄰接矩陣 fillchar(a,sizeof(a),

5、0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); end;function tporder:boolean; /拓?fù)渑判?,成功則返回 true var i,j,k:integer; into:array1.maxn of byte; begintporder:=false;fillchar(into,sizeof(into),0); for i:=1 to n do for j:=1 to n doif mapi,j>0 then inc(intoj); / 計(jì)算各點(diǎn)的入度for i:=1 to n do beginj:=1;第

6、2頁共4頁while (j<=n)and(intoj<>0) do inc(j); / 掃描入度為 0 的點(diǎn)if j>n then exit; / 不能拓?fù)渑判騛i:=j; / 記錄刪除點(diǎn)的編號，即拓?fù)湎盗衖ntoj:=$ff; / 刪除點(diǎn) j ，其入度賦為 255for k:=1 to n doif mapj,k>0 then dec(intok); / 去掉所有 j 指向的點(diǎn)，即那些點(diǎn)入度都減去 1 end; tporder:=true; /能夠拓?fù)渑判騟nd;procedure calc; /動(dòng)態(tài)規(guī)劃求最長路徑（關(guān)鍵路徑）var i,j:integer;be

7、ginba1:=0;ca1:=0; /初始化for i:=2 to n do / 枚舉階段for j:= 1 to i-1 do / 枚舉狀態(tài)if baj+mapaj,ai>bai then /決策beginbai:=baj+mapaj,ai;cai:=aj;end;end;procedure print; /輸出關(guān)鍵路徑var i,j,k:integer;d:array1.maxn of 0.maxn;beginwriteln('long=',ban); / 輸出最長距離，即終點(diǎn)到起點(diǎn)的最短距離k:=can;i:=0;/此處 K 是終點(diǎn)的前一個(gè)點(diǎn)的編號while k<>0 do / 統(tǒng)計(jì)除了終點(diǎn)外，關(guān)鍵路徑上有幾個(gè)點(diǎn)，存在i:=i+1;di:=k;k:=ck end; / 把關(guān)鍵路徑中的系列點(diǎn)倒序存在數(shù)組i 中 begind 中 for j:=idownto 1 do /輸出write(dj,' '); / 正好順序輸出writeln(an) / 輸出終點(diǎn)end;beginassign(input,'gjlj.in');reset(input);assign(output,'gjlj.out