圖論算法經(jīng)典

1、圖論算法最小生成樹算法(Prim算法)單源最短路徑算法(Dijkstra算法)任意結(jié)點(diǎn)最短路徑算法(Floyd算法)求有向帶權(quán)圖的所有環(huán)Bellman-Ford算法計算圖的連通性計算最佳連通分支計算拓?fù)湫蛄袌D論算法習(xí)題網(wǎng)絡(luò)建設(shè)問題最短變換問題挖地雷烏托邦城市烏托邦交通中心某大學(xué)準(zhǔn)備在校園網(wǎng)中構(gòu)建校園網(wǎng)絡(luò)，已知在校園網(wǎng)中選好了N（N<1000）個點(diǎn)，并準(zhǔn)備在這些點(diǎn)安裝網(wǎng)絡(luò)設(shè)備和電腦。若要將N個點(diǎn)互相連接起來，問怎樣布線才能使得總距離最短，兩點(diǎn)間的布線長度等于這兩個點(diǎn)的幾何距離?！据斎搿縩etwork.in輸入文件的第一行為一個正整數(shù)N(1N100)。接下來N行，每行2個數(shù)U,V ，表示坐標(biāo)

2、。【輸出】network.out輸出最短路徑距離（保留兩位小數(shù)）【樣例數(shù)據(jù)】  【輸入】50 00 10 -11 0-1 0【輸出】4.00 思路分析：此題可以應(yīng)用PRIM算法解決，關(guān)鍵是根據(jù)輸入文件算出圖的鄰接矩陣，然后可以直接應(yīng)用PRIM算法。program network;const vmax=100;var w:array1.vmax,1.vmaxof real; x,y:array1.vmax of real; i,j,k,v,e:integer; sum:real;procedure prim(v0:integer); var flag:array1.vmax of bo

3、olean; min:real; prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flagv0:=true; for i:=1 to v-1 do begin min:=1e38; for k:=1 to v do if flagk then for j:=1 to v do if (not flagj) and (wk,j<min) and (wk,j<>0) then begin min:=wk,j; nextk:=j; prevk:=k; end; if min<>1e10 then

4、 begin flagnextk:=true; writeln(prevk,' ',nextk,' ',min:0:2); 此部分輸出每個結(jié)點(diǎn)對的距離，因題目不要求所以不輸出。 sum:=sum+min; end; end; end;primbegin assign(input,'network.in'); reset(input); assign(output,'network.out'); rewrite(output); fillchar(w,sizeof(w),0); readln(v); for i:=1 to v do

5、 readln(xi,yi); for i:=1 to v do 計算圖的鄰接矩陣 begin for j:=i+1 to v do begin wi,j:=sqrt(sqr(xi-xj)+sqr(yi-yj); wj,i:=wi,j; end; end; sum:=0; prim(1); writeln(sum:0:2); close(input); close(output);end.無向圖的生成樹就是從圖的邊集中選擇一些邊，使得這些邊構(gòu)成一個連通無環(huán)圖，也就是樹。如果給每一條邊加一個權(quán)，所有生成樹中權(quán)和最小的生成樹稱為最小生成樹。【Prim算法思想】任意時刻的中間結(jié)果都是一棵樹，每次花費(fèi)

6、最小的代價，用一條邊把不在樹中的結(jié)點(diǎn)加進(jìn)來?！咀钚∩蓸渌惴▽?shí)例】    現(xiàn)有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個城市間的連通關(guān)系，邊上的權(quán)代表公路造價。在分析了這張圖后發(fā)現(xiàn)，任一對城市都是連通的。現(xiàn)在要求用公路把所有城市聯(lián)系起來，如何設(shè)計可使得工程的總造價最少？【輸入】 第一行兩個數(shù)v(v<=200),e，分別代表城市數(shù)和邊數(shù) 以下e行，每行為兩個頂點(diǎn)和它們之間的邊權(quán)w(w<1000)?！据敵觥?v-1行，每行為兩個城市的序號，表明這兩個城市間建一條公路，再加該公路的造價。 【輸入樣例】 6 10 1 2 10 1 5 19 1 6 21

7、2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【輸出樣例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 原  圖 最小生成樹program prim_example;Const   vmax=200var   w:array1.vmax,1.vmaxof integer;   i,j,k,v,e:integer;procedure prim(v0:integer); v0是開始結(jié)點(diǎn)  var    flag:array

8、1.vmax of boolean;    min,prevk,nextk:integer;  begin    fillchar(flag,sizeof(flag),false);    flagv0:=true; 先選出v0    for i:=1 to v-1 do 一共尋找v-1條邊      begin        min:=maxin

9、t;          for k:=1 to v do            if flagk then 找已在集合中的頂點(diǎn)              for j:=1 to v do 求滿足條件的邊的最小值     

10、            if (not(flagj) and (wk,j<min) and (wk,j<>0)                    then begin         &#

11、160;                min:=wk,j; 記下最小值                          nextk:=j;     

12、;                     prevk:=k;                         end;   &#

13、160;             if min<>maxint                    then begin             

14、             flagnextk:=true; 最小值對應(yīng)頂點(diǎn)進(jìn)入集合                          writeln(prevk,' ',nextk, ',min);

15、0;                        end;             end;for   end;primbegin  assign(input,'prim.in');  res

16、et(input);  assign(output,'prim.out');  rewrite(output);  fillchar(w,sizeof(w),0);  readln(v,e);  for k:=1 to e do    begin      read(i,j);      readln(wi,j);      wj,i:=wi,j;&#

17、160;   end;  prim(1);  close(input);  close(output);end.設(shè)圖G=(V,E)是一個有向圖,它的每一條邊(U,V)都有一個非負(fù)權(quán)W(U,V)，在G中指定一個結(jié)點(diǎn)V0，要求從V0到G的每一個結(jié)點(diǎn)Vj的最短路徑找出來（或指出不存在）。    由于源結(jié)點(diǎn)V0是給定的，所謂稱為單源最短路徑。【Dijkstra算法思想】   把所有結(jié)點(diǎn)分為兩組。    第一組：包含已確定最短路徑的結(jié)點(diǎn)。    第二組：包含尚未確定

18、最短路徑的結(jié)點(diǎn)。    按最短路徑長度遞增的順序把第二組的結(jié)點(diǎn)加到第一組中去，直到V0可達(dá)的所有結(jié)點(diǎn)都包含于第一組中。在這個過程中，總保持從V0到第一組各結(jié)點(diǎn)的最短路徑長度都不大于從V0到第二組任何結(jié)點(diǎn)的路徑長度。 【單源最短路徑算法實(shí)例】    現(xiàn)有一張縣城的城鎮(zhèn)地圖，圖中的頂點(diǎn)為城鎮(zhèn)，無向邊代表兩個城鎮(zhèn)間的連通關(guān)系，邊上的權(quán)為公路造價，縣城所在的城鎮(zhèn)為v0。由于該縣經(jīng)濟(jì)比較落后，因此公路建設(shè)只能從縣城開始規(guī)劃。規(guī)劃的要求是所有可到達(dá)縣城的城鎮(zhèn)必須建設(shè)一條通往縣城的汽車線路，該線路的工程總造價必須最少?！据斎搿?第一行一個整數(shù)v，代表城鎮(zhèn)數(shù)，

19、縣城編號為1。 第二行是一個整數(shù)e，表示有向邊數(shù)。 以下e行，每行為兩個城鎮(zhèn)編號和它們之間的公路造價。 【輸出】 v-1行，每行為兩個城市的序號，表明這兩個城市間建一條公路。 【輸入樣例】 610 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【輸出樣例】 1 22 32 41 51 6            原    圖從第1點(diǎn)出發(fā)的最短路徑program dijks

20、tra_example;const  vmax=100;type  path=record                  此記錄類型用于記錄每一個結(jié)點(diǎn)與v0的距離和其父結(jié)點(diǎn)        length:integer;        pre:0.vmax; 

21、;      end;var  w:array1.vmax,1.vmax of integer;  dist:array1.vmax of path;  v,e,u,i,j,x,y:integer;procedure init;  begin    assign(input,'dijkstra.in');    reset(input);    assign(output,'dijkstra.

22、out');    rewrite(output);    readln(v);    readln(e);    for i:=1 to v do      for j:=1 to v do        if i<>j          then

23、 wi,j:=30000    30000只是一個較大的數(shù)的意思，實(shí)際應(yīng)用于應(yīng)該根據(jù)題目中給出的取值范圍賦予一個充分大的數(shù)          else wi,j:=0;    for i:=1 to e do      begin        read(x,y);      &

24、#160; readln(wx,y);        wy,x:=wx,y;      end;  end;procedure dijkstra(v0:integer);  var    min:integer;  begin    wv0,v0:=1;           &#

25、160;    v0首先進(jìn)入第一組    for i:=1 to v do     begin       disti.length:=wv0,i;   計算每個結(jié)點(diǎn)的距離值       if disti.length<>30000         then dist

26、i.pre:=v0     如和v0直接有路，則置前驅(qū)結(jié)點(diǎn)為v0         else disti.pre:=0;      end;  repeat    min:=30000;    u:=0;    for i:=1 to v do       &#

27、160;     找最短距離      if (wi,i=0) and (disti.length<min)         then begin               u:=i;        &

28、#160;      min:=disti.length;             end;    if u<>0      then begin            wu,u:=1;   

29、60;        for i:=1 to v do         重新計算其他結(jié)點(diǎn)的距離值              if (wi,i=0) and (disti.length>distu.length+wu,i)        

30、;        then begin                      disti.length:=distu.length+wu,i;              

31、60;       disti.pre:=u;                     end;            end;  until u=0; end;begin  init; 

32、v0:=1;  dijkstra(v0);  for i:=1 to v do    begin      if (i<>v0) and (disti.length<>30000)         then write(disti.pre,' ',i);    end;  close(input);  close(output)

33、;end.設(shè)圖G=(V,E)是一個有向圖,對于每對結(jié)點(diǎn)(U,V),找出從U到V的最短路徑?！綟loyd算法思想】    利用一個三重循環(huán)產(chǎn)生一個存儲每個結(jié)點(diǎn)最短距離的矩陣.【Floyd算法實(shí)例】    現(xiàn)有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個城市間的連通關(guān)系，邊上的權(quán)代表城市之間的距離。求每個城市的最短距離【輸入】 第一行兩個數(shù)v,e，分別代表城市數(shù)和邊數(shù) 以下e行，每行為兩個頂點(diǎn)和它們之間的邊權(quán)。 【輸出】 所有可能連接的城市的最短距離。 【輸入樣例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4

34、 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【輸出樣例】 1 2 101 3 151 4 161 5 191 6 212 3 52 4 62 5 242 6 113 4 63 5 243 6 164 5 184 6 145 6 32  program floyd_example;const  maxn=10;var  n,s,t,i,j:integer;  dist:array1.maxn,1.maxn of real;  prev:array1.maxn,1.maxn of 0.maxn;procedure in

35、it;  var    m,i,u,v:integer;  begin    assign(input,'floyd.in');    reset(input);    assign(output,'floyd.out');    rewrite(output);    readln(n,m);    fillchar(prev,siz

36、eof(prev),0);    for u:=1 to n do     for v:=1 to n do       distu,v:=1e10;    for i:=1 to m do      begin        readln(u,v,distu,v);    &#

37、160;   distv,u:=distu,v;        prevu,v:=u;        prevv,u:=v;     end;  end;initprocedure floyd;  var    i,j,k:integer;  begin    for k:=1 to n do &#

38、160;    for i:=1 to n do         for j:=1 to n do           if (disti,k+distk,j<disti,j)               then  begin &#

39、160;               disti,j:=disti,k+distk,j;                 previ,j:=prevk,j;            

40、    end;  end;floydprocedure print(i,j:integer);  begin    if i=j      then write(i)      else if previ,j=0             then write('No Solution!&#

41、39;)             else begin                  print(i,previ,j);               

42、60;  write('->',j);                  end;  end;printbegin  init;  floyd;  for i:=1 to n do    for j:=i+1 to n do      begin  

43、0;     write(i,' ',j,' ');        write(disti,j:0:0,' ');        print(i,j);        writeln;      end;  close(input);

44、0; close(output);end.求有向圖的所有環(huán),此問題包括了求最大環(huán)或者最小環(huán)?！据斎搿? 第一行兩個數(shù)v,e，分別代表圖的頂點(diǎn)數(shù)和邊數(shù)，以下e行，每行為有連接的兩個頂點(diǎn)和權(quán)。 【輸出】  頂點(diǎn)編號和環(huán)的長度以及包含該頂點(diǎn)的環(huán)的路徑。 【輸入樣例】 huan.in5 71 2 22 1 12 5 43 2 53 4 74 1 35 4 6【輸出樣例】 huan.out1 3 1->22 3 2->14 15 4->1->2->55 15 5->4->1->2  program huan;const

45、0; maxn=90;var  n,s,t,i,j:integer;  dist:array1.maxn,1.maxn of real;  prev:array1.maxn,1.maxn of 0.maxn;procedure init;  var    m,i,u,v:integer;  begin    assign(input,'huan.in');    reset(input);    assign(

46、output,'huan.out');    rewrite(output);    readln(n,m);    fillchar(prev,sizeof(prev),0);    for u:=1 to n do      for v:=1 to n do        distu,v:=1e10;   &

47、#160; for i:=1 to m do      begin        readln(u,v,distu,v);        prevu,v:=u;      end;    end;procedure floyd; var   i,j,k:integer; begin 

48、60; for k:=1 to n do     for i:=1 to n do       for j:=1 to n do         if (disti,k+distk,j<disti,j)              then  begin  

49、0;            disti,j:=disti,k+distk,j;               previ,j:=prevk,j;              end;  end;floydproce

50、dure print(i,j:integer);  begin   if i=j     then write(i)     else if previ,j=0            then write('No Circle!')           

51、 else begin                print(i,previ,j);                write('->',j);           

52、;     end;  end;printbegin  init;  floyd;  for i:=1 to n do     begin        if disti,i<>1e10          then        

53、;    begin              write(i,' ');              write(disti,i:0:0,' ');           

54、;   print(i,previ,i);              writeln;            end;      end;  close(input);  close(output);end.輸入一張無向圖，指出該圖中哪些結(jié)點(diǎn)對之間有路。該問題通常采用傳

55、遞閉包的計算方法?！据斎搿?#160;   n(頂點(diǎn)數(shù)，1n20)    e(邊數(shù)，1e210)    以下e行，每行為有邊連接的一對頂點(diǎn)【輸出】    k行，每行兩個數(shù)，為存在通路的頂點(diǎn)對序號i,j(i<j) 【輸入樣例】 651 51 62 34 65 6【輸出樣例】 1 41 51 62 34 54 65 6  program bibao_example;const  maxv=20;var  link,longlink:array1.maxv

56、,1.maxv of boolean;  v,e,k,i,j:integer;procedure init;  begin    assign(input,'bibao.in');    reset(input);    assign(output,'bibao.out');    rewrite(output);    fillchar(longlink,sizeof(longlink),0)

57、;    fillchar(link,sizeof(link),0);    readln(v);    readln(e);    for k:=1 to e do     begin      readln(i,j);      linki,j:=true;      

58、60;     因?yàn)闆]有權(quán)，所以有布爾型表示連通關(guān)系，能提高運(yùn)算速度      linkj,i:=true;     end;  end;initprocedure bibao;  begin    longlink:=link;    for k:=1 to v do          

59、      枚舉中間頂點(diǎn)      for i:=1 to v do              枚舉所有頂點(diǎn)對          for j:=1 to v do          

60、0; 計算頂點(diǎn)i和頂點(diǎn)j的連通情況           longlinki,j:=longlinki,j or (longlinki,k and longlinkk,j);  end;bibaoprocedure out;  begin   for i:=1 to v-1 do    for j:=i+1 to v do      if longlinki,j 

61、60;      then writeln(i,' ',j);  end;outbeginmain  init;  bibao;  out;  close(input);  close(output);end.在一張頂點(diǎn)帶權(quán)的無向圖中，計算含頂點(diǎn)數(shù)最多的一個連通分支和頂點(diǎn)權(quán)和最大的連通分支?！据斎搿?#160;   n(頂點(diǎn)數(shù)，1n20)    以下n行，其中第i行是頂點(diǎn)i的權(quán)    e(邊

62、數(shù)，1e210)    以下e行，每行為有邊連接的一對頂點(diǎn)【輸出】    含頂點(diǎn)數(shù)最多的一個連通分支    頂點(diǎn)權(quán)和最大的一個連通分支 【輸入樣例】 62102085751 51 62 34 65 6【輸出樣例】 1->5->6->4->2->3->  program liantong_example;const  maxv=20;var  link,longlink:array1.maxv,1.maxv of boolean; 

63、 f:array1.maxv of boolean;  w:array1.maxv of integer;  v,e,k,i,j,s,best,besti,max,maxk:integer;procedure init;  begin   assign(input,'liantong.in');   reset(input);   assign(output,'liantong.out');   rewrite(output);  

64、fillchar(longlink,sizeof(longlink),0);   fillchar(link,sizeof(link),0);   readln(v);   for i:=1 to v do     readln(wi);   readln(e);   for k:=1 to e do     begin       readln(i,j);

65、       linki,j:=true;       linkj,i:=true;     end;  end;initprocedure bibao;  begin    longlink:=link;    for k:=1 to v do      for i:=1 to v do 

66、0;     for j:=1 to v do        longlinki,j:=longlinki,j or (longlinki,k and longlinkk,j);  end;bibaoprocedure dfs(i:integer);         深度優(yōu)先搜索，用于輸出路徑  begin    write(i,'->'

67、;);    fi:=true;    for j:=1 to v do      if (not fj) and longlinki,j         then dfs(j);  end;dfsbeginmain  init;  bibao;  for i:=1 to v do    begin   &#

68、160;  k:=0;s:=0;      for j:=1 to v do          計算頂點(diǎn)i所在連通分支中的頂點(diǎn)總數(shù)和頂點(diǎn)的權(quán)和        if longlinki,j          then begin     &#

69、160;           k:=k+1;                 s:=s+wj;               end;     

70、0;  if k>best                求出頂點(diǎn)數(shù)的最大值            then begin                 

71、  best:=k;                   besti:=i;                 end;        if s>max  

72、               求出頂點(diǎn)權(quán)和的最大值            then begin                   max:=s;  

73、                 maxk:=i;                 end;        if k=v then break;      en

74、d;   fillchar(f,sizeof(f),false);  結(jié)點(diǎn)是否訪問數(shù)組初始化   dfs(besti);   writeln;   fillchar(f,sizeof(f),false);   dfs(maxk);  close(input);  close(output);end.所謂拓?fù)湫蛄?，就是有向圖的最長路徑問題，如果圖中存在環(huán)，則最長路徑是無法求得的，所以有拓?fù)湫蛄械挠邢驁D不可以存在環(huán)。具體定義如下：    給

75、出有向圖G=（V，E），若結(jié)點(diǎn)的線形序列V1,V2,.Vn滿足條件：對于i,j(1j<in)，Vi和Vj之間沒有邊。求線形序列V1,V2,.Vn的過程就稱為拓?fù)渑判?，這個線形序列就稱為拓?fù)湫蛄?。【拓?fù)渑判蛑饕枷搿?#160;有向圖可以拓?fù)渑判虻臈l件是：圖中沒有環(huán)。 具體方法：  從圖中選擇一個入度為0的點(diǎn)加入拓?fù)湫蛄小?#160; 從圖中刪除該結(jié)點(diǎn)以及它的所有出邊（即與之相鄰點(diǎn)入度減1）。 反復(fù)執(zhí)行這兩個步驟，直到所有結(jié)點(diǎn)都已經(jīng)進(jìn)入拓?fù)湫蛄小！緦?shí)例：士兵排隊(duì)問題】有n個士兵(1n26)，依次編號為A,B,C,.，隊(duì)列訓(xùn)練時，指揮官要把一些士兵從高到矮排成一

76、行。但現(xiàn)在指揮官不能直接獲得每個人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果，記作（p1>p2）。例如A>B，B>D，F(xiàn)>D，對應(yīng)的排隊(duì)方案有三個：AFBD，F(xiàn)ABD，ABFD【輸入】    k行，每行a b，表示a>b【輸出】    一個可行的排隊(duì)方案 【輸入樣例】 A BB DF D【輸出樣例】 ABFD  program soldier_sort;var  w:array'A'.'Z','A'.'Z' of

77、0.1;  d:array'A'.'Z' of integer;         記錄頂點(diǎn)入度的數(shù)組  s:set of 'A'.'Z'  a,b,ch:char;  m,n:string;  i,j,k:integer;begin  assign(input,'tuopu.in');  reset(input);  assign(output,'t

78、uopu.out');  rewrite(output);  s:=;  while not eof(input) do    begin     readln(a,ch,b);     s:=s+a,b;        計算士兵名集合     wa,b:=1;     db:=db+1; 

79、     累計頂點(diǎn)b的入度    end;  m:=''  for a:='A' to 'Z' do  if a in s    then m:=m+a;        產(chǎn)生士兵名字符集  k:=length(m);         求得士兵人數(shù)  n

80、:=''                拓?fù)湫蛄谐跏紴榭?#160; for i:=1 to k do    begin     j:=1;     while (dmj>0) and (j<=k) do   搜索第i個入度為0的士兵的頂點(diǎn)序號j    

81、;     j:=j+1;     if j>k                            若不存在入度為0的頂點(diǎn)，則無法拓?fù)渑判蚴?#160;      then begin&#

82、160;            writeln('Fault!');               break;            end;     n:=n+mj;  &

83、#160;      入度為0的頂點(diǎn)進(jìn)入拓?fù)湫蛄衝     a:=mj;           刪去頂點(diǎn)j     da:=maxint;     for j:=1 to k do   與a相連的頂點(diǎn)入度減1     if wa,mj>0  &#

84、160;     then dmj:=dmj-1;   end;for  writeln(n);  close(input);  close(output);end.在一個地圖上有n(n20)個地窖,每個地窖中埋有一定數(shù)量的地雷,給出地窖之間的聯(lián)系路徑。當(dāng)?shù)亟褬O其連接的數(shù)據(jù)給出之后,某人可以從任一處開始挖地雷,然后可以沿著指出的連接往下挖(僅能選擇一條路徑)，挖雷的過程中允許某人重復(fù)經(jīng)過地窖。當(dāng)無連接時，挖地雷工作結(jié)束。請編程設(shè)計一個挖地雷的方案，使某人能挖到的最多的地雷。 【輸入文件】miner.in n(地窖個數(shù))v1 v2 v3 . vn (每個地窖的地雷數(shù))a(1,2) . a(1,n)a(2,3) . a(2,n) . . .a(n-1,n) (表示地窖之間連接路徑，其中a(i,j)表示地窖i,j之間是否有通路，若有通路，則a(i,j)=1，若無通路，則a(i,j)=0）【輸出文件】miner.outR1-R2-.-Rk(挖地雷的順序)Max(挖的地雷總數(shù)) 【樣例數(shù)據(jù)】  【輸入】miner.in62 10 20 8 5 70 0 0 1 11 0 0 00