图论算法经典

1、图论算法最小生成树算法(Prim算法)单源最短路径算法(Dijkstra算法)任意结点最短路径算法(Floyd算法)求有向带权图的所有环Bellman-Ford算法计算图的连通性计算最佳连通分支计算拓扑序列图论算法习题网络建设问题最短变换问题挖地雷乌托邦城市乌托邦交通中心某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N<1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。【输入】network.in输入文件的第一行为一个正整数N(1N100)。接下来N行，每行2个数U,V ，表示坐标

2、。【输出】network.out输出最短路径距离（保留两位小数）【样例数据】  【输入】50 00 10 -11 0-1 0【输出】4.00 思路分析：此题可以应用PRIM算法解决，关键是根据输入文件算出图的邻接矩阵，然后可以直接应用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); 此部分输出每个结点对的距离，因题目不要求所以不输出。 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.无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费

6、最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】    现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】 第一行两个数v(v<=200),e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权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是开始结点  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 找已在集合中的顶点              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; 最小值对应顶点进入集合                          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.设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在G中指定一个结点V0，要求从V0到G的每一个结点Vj的最短路径找出来（或指出不存在）。    由于源结点V0是给定的，所谓称为单源最短路径。【Dijkstra算法思想】   把所有结点分为两组。    第一组：包含已确定最短路径的结点。    第二组：包含尚未确定

18、最短路径的结点。    按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。 【单源最短路径算法实例】    现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。【输入】 第一行一个整数v，代表城镇数，

19、县城编号为1。 第二行是一个整数e，表示有向边数。 以下e行，每行为两个城镇编号和它们之间的公路造价。 【输出】 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点出发的最短路径program dijks

20、tra_example;const  vmax=100;type  path=record                  此记录类型用于记录每一个结点与v0的距离和其父结点        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只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数          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首先进入第一组    for i:=1 to v do     begin       disti.length:=wv0,i;   计算每个结点的距离值       if disti.length<>30000         then dist

26、i.pre:=v0     如和v0直接有路，则置前驱结点为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         重新计算其他结点的距离值              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.设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。【Floyd算法思想】    利用一个三重循环产生一个存储每个结点最短距离的矩阵.【Floyd算法实例】    现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。 【输出】 所有可能连接的城市的最短距离。 【输入样例】 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.求有向图的所有环,此问题包括了求最大环或者最小环。【输入】  第一行两个数v,e，分别代表图的顶点数和边数，以下e行，每行为有连接的两个顶点和权。 【输出】  顶点编号和环的长度以及包含该顶点的环的路径。 【输入样例】 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.输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传

55、递闭包的计算方法。【输入】    n(顶点数，1n20)    e(边数，1e210)    以下e行，每行为有边连接的一对顶点【输出】    k行，每行两个数，为存在通路的顶点对序号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;     因为没有权，所以有布尔型表示连通关系，能提高运算速度      linkj,i:=true;     end;  end;initprocedure bibao;  begin    longlink:=link;    for k:=1 to v do          

59、      枚举中间顶点      for i:=1 to v do              枚举所有顶点对          for j:=1 to v do          

60、0; 计算顶点i和顶点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.在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。【输入】    n(顶点数，1n20)    以下n行，其中第i行是顶点i的权    e(边

62、数，1e210)    以下e行，每行为有边连接的一对顶点【输出】    含顶点数最多的一个连通分支    顶点权和最大的一个连通分支 【输入样例】 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);         深度优先搜索，用于输出路径  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          计算顶点i所在连通分支中的顶点总数和顶点的权和        if longlinki,j          then begin     &#

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

70、0;  if k>best                求出顶点数的最大值            then begin                 

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

72、               求出顶点权和的最大值            then begin                   max:=s;  

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

74、d;   fillchar(f,sizeof(f),false);  结点是否访问数组初始化   dfs(besti);   writeln;   fillchar(f,sizeof(f),false);   dfs(maxk);  close(input);  close(output);end.所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下：    给

75、出有向图G=（V，E），若结点的线形序列V1,V2,.Vn满足条件：对于i,j(1j<in)，Vi和Vj之间没有边。求线形序列V1,V2,.Vn的过程就称为拓扑排序，这个线形序列就称为拓扑序列。【拓扑排序主要思想】 有向图可以拓扑排序的条件是：图中没有环。 具体方法：  从图中选择一个入度为0的点加入拓扑序列。  从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。 反复执行这两个步骤，直到所有结点都已经进入拓扑序列。【实例：士兵排队问题】有n个士兵(1n26)，依次编号为A,B,C,.，队列训练时，指挥官要把一些士兵从高到矮排成一

76、行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD【输入】    k行，每行a b，表示a>b【输出】    一个可行的排队方案 【输入样例】 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;         记录顶点入度的数组  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、     累计顶点b的入度    end;  m:=''  for a:='A' to 'Z' do  if a in s    then m:=m+a;        产生士兵名字符集  k:=length(m);         求得士兵人数  n

80、:=''                拓扑序列初始为空  for i:=1 to k do    begin     j:=1;     while (dmj>0) and (j<=k) do   搜索第i个入度为0的士兵的顶点序号j    

81、;     j:=j+1;     if j>k                            若不存在入度为0的顶点，则无法拓扑排序失败       then begin&#

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

83、#160;      入度为0的顶点进入拓扑序列n     a:=mj;           删去顶点j     da:=maxint;     for j:=1 to k do   与a相连的顶点入度减1     if wa,mj>0  &#

84、160;     then dmj:=dmj-1;   end;for  writeln(n);  close(input);  close(output);end.在一个地图上有n(n20)个地窖,每个地窖中埋有一定数量的地雷,给出地窖之间的联系路径。当地窖极其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。 【输入文件】miner.in n(地窖个数)v1 v2 v3 . vn (每个地窖的地雷数)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(挖的地雷总数) 【样例数据】  【输入】miner.in62 10 20 8 5 70 0 0 1 11 0 0 00