1、趣谈数据结构十趣谈数据结构（十）福州一中 陈颖 本讲通过几个例子，着重讲解图的两种存储结构邻接表和邻接矩阵的使用，介绍图应用中常见的几种问题的处理方法及算法。例1 有如图1所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能有 涂色方案。分析:本题实际上就是著名的地图四色问题。无论地图多么复杂，只需用四种颜色就可以将相邻的区域分开。图 1为了解题方便，我们可以把七巧板上每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这样，该问题就转化为图的问题了。算法步骤:按顺序分别对号、号、.、号区域进行试
2、探性涂色，用、号代表种颜色。数据采用邻接矩阵。对某一区域涂上与其相邻区域不同的颜色。若使用种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。转步骤继续涂色，直到全部结束为止，输出。源程序如下:program four-colors(input,output,fdat);constmax=10;typegradat=array1.max,1.max of byte;vardata:gradat;n:byte;color:array1.max of byte;total:integer;procedure getdata;输入数据varname:string12;fdat:text;i
3、,j:byte;beginwrite(use which file?);readln(name);assign(fdat,name);reset(fdat);read(fdat,n);for i:=1 to n dofor j:=1 to n doread(fdat,datai,j);for i:=1 to n dobeginfor j:=1 to n do write(datai,j:5);writeln;end;writeln;end;function colorsame(s:byte):boolean;判断相邻点是否同色vari:byte;begincolorsame:=false;fo
4、r i:=1 to s-1 doif (datai,s=1) and (colori=colors) then colorsame:=true;end;procedure print;输出vari:byte;beginfor i:=1 to n do write(colori:2);inc(total);writeln( con:,total);end;procedure try(s:byte);递归搜索vari:byte;beginif s7 then printelsebegini:=0;repeatinc(i);colors:=i;if not(colorsame(s) then try
5、(s+1);until i=4end;end;begin 主源程序如下getdata;total:=0;try(1);writeln(Total=,total);readln;end.fdat文件内容:70 1 0 0 1 0 11 0 0 1 0 1 00 0 0 0 0 1 10 1 0 0 0 1 11 0 0 0 0 0 10 1 1 1 0 0 01 0 1 1 1 0 0例2 对图2从V1点出发，沿着边系统地访问该图中其它所有的顶点一次且仅一 次。(用两种不同的解法) 图2 图 3分析:从图上某点出发，沿边访问图中其它所有的顶点一次且仅一次，称为图的遍历。图的遍历有两种方式：深度优
6、先搜索遍历与广度优先搜索遍历。算法步骤:（一）深度优先搜索遍历算法以给定的某个顶点V0为起始点，访问该顶点；选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复上述过程；当到达一个其所有邻接的顶点都已被访问过的顶点Vi时，就退回到新近被访问过的顶点Vi-1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程；直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。图13.14中从出发的一种深度优先搜索访问顺序：-（二）广度优先搜索遍历算法从图中的某一顶点V0开始，先访问V0；访问所有与V
7、0相邻接的顶点V1，V2，.，Vt；依次访问与V1，V2，.，Vt相邻接的所有未曾访问过的顶点；循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。图13.14中，从出发的一种广度优先搜索访问顺序为：-源程序如下:源程序如下中数据采用邻接表方式表示。邻接表如图13.15所示。存储邻接表数据需要三个变量，一个存储结点的内容，一个存储结点指向下一个结点的指针，一个存储每个链表的链头指针。设数组变量A(i,0)存放结点，A(i,1)存放结点的指针，存放链头指针。数据存放形式如表1所示。 表1 源程序如下：program bianli(input,
8、output,fdat);constmax=10;typegradat=array1.max,1.max of integer;way=set of 1.max;vardata:gradat;n,k:byte;path:array1.max of byte;already:way;m:integer;procedure getdata;输入数据varname:string12;fdat:text;i,j:byte;beginwrite(use which file?);readln(name);assign(fdat,name);reset(fdat);read(fdat,n);for i:=
9、1 to n dobeginj:=0;repeatinc(j);read(fdat,datai,j);until datai,j=0;end;for i:=1 to n dobeginj:=1;write(,i:2, );while datai,j0 dobeginwrite(datai,j:3);inc(j);end;writeln;end;end;procedure print;输出vari:byte;beginfor i:=1 to n do write(pathi:2);writeln;end;procedure width(s:byte);广度优先搜索遍历varuseful,next
10、:way;i,j:byte;begink:=1;pathk:=s;useful:=s;already:=s;next:=;repeatfor i:=1 to n doif i in useful thenbeginj:=1;repeatif not(datai,j in already) thenbeginnext:=next+datai,j;already:=already+datai,j;inc(k);pathk:=datai,j;end;inc(j)until datai,j=0;end;useful:=next;next:=;until k=n;end;procedure deepth
11、(s:byte);深度优先搜索遍历vari:byte;begini:=1;inc(k);pathk:=s;already:=already+s;while datas,i0 dobeginif not(datas,i in already)then deepth(datas,i);inc(i);end;end;begingetdata;k:=0;already:=;repeatwrite(Which do you want to begin:);readln(m);until (m0) and (m=0时，解决最短路径问题的比较好的方法是Dijkstra方法。 它是荷兰计算机科学家（E.W.D
12、ijkstra）于1959年提出的。这个方法不仅求出了从A到顶点B的最短路径，而且求出了从A到各顶点的最短路径。算法步骤：从V1开始，给每一个顶点赋予一个标号，标号分为两种：(1)T标号-V1到该顶点的最短路径的上界（临时标号）；(2)P标号-V1到该顶点的最短路径（固定标号）。若某一顶点已得到P标号，则表明已求出V1到该点的最路径，凡未得到P标号的顶点，一律标上T标号。算法的每一步把某一顶点的T标号改变为P标号，最多经过（）步（为顶点个数），即可得到从V1到每一个顶点的最短路径。在初始状态下，令P(V1)=0，T(Vi)=+（1，2，3，.，）， 反复执行下面两个步骤；设Vi是已经得到P标号
13、的点，考虑所有满足下列条件的顶点Vi的集合B:B Vj|(Vi,Vj) E且Vj是T标号将集合B中的每一个顶点Vj的T标号修改为:minT(Vj),P(Vi)+W(i,j)若G中已没有T标号的顶点，则结束，否则，将集合B中最小者的T标号改变为P 标号，然后转到。下面，以求1到7的最短路径为例，说明Dijkstra方法：开始，令P(V1)0，T(Vj)（j=1,2,3,.,7）第一步：考虑所有与V1相联且标有T标号的点的集合：B=V2,V3,V4；修改集合B中元素的T标号T(V2)=minT(V2)，P(V1)+W(1,2)=min+，2=2T(V3)=minT(V3)，P(V1)+W(1,3)
14、=min+，5=5T(V4)=minT(V4)，P(V1)+W(1,4)=min+，3=3将其中最小者改为标号：P(2)=2第二步：考虑所有与V1，V2相联且标有T标号的点集合：B=V3，V4，V6；修改集合B中元素的T标号T(V3)=minT(V3)，P(2)+W(2,3)=min5,4=4T(V4)=3 (同前面求法)T(V6)=minT(V6)，P(2)+W(2,6)=min+，9=9将其中最小者改变为P标号，P(V4)=3第三步：考虑所有与V1,V2,V4相联且标有T标号的点的集合：B=V3，V5，V6；修改集合B中元素的T标号T(V3)=4T(V5)=minT(V5)，P(V4)+W
15、(4,5)=min+，8=8T(V6)=9将其中最小者改变为P标号：P(V3)=4第四步：考虑所有与V1，V2，V3，V4相联且标有T标号的点的集合：B=V5，V6；修改集合B中的元素的T标号T(V5)=minT(V5)，P(V3)+W(3,5)=min8，7=7T(V6)=minT(V6)，P(V3)+W(3,6)=min9，9=9将其中最小者改变为P标号：P(V5)=7第五步：考虑所有与V1，V2，V3，V4，V5相联且标有T标号的点的集合：B=V6，V7；修改集合B中的元素的T标号T(V6)=minT(V6)，P(V5)+W(5,6)=min9，8=8T(V7)=minT(V7)，P(V
16、5)+W(5,7)=min+，14=14将其中最小者改变为T标号：P(V6)=8第六步：考虑所有与V1，V2，V3，V4，V5，V6相联且标有T标号的点的集合：B=V7；修改集合中B元素的T标号T(V7)=minT(V7)，P(V6)+W(6,7)=min14，13=13将其中最小者改变为P标号：P(V7)=13至此，所有顶点的标号均已改变为标号了，说明到各顶点的最短路径已全部找到。源程序如下：program least way;constmax=10;typegradat=array1.max,1.max of real;way=set of 1.max;vara,b:byte;n:byte
17、;data:gradat;path,path1:array1.max of byte;least:real;k:byte;procedure getdata;输入数据varname:string12;fdat:text;i,j:byte;beginwrite(use which file?);readln(name);assign(fdat,name);reset(fdat);read(fdat,n);for i:=1 to n dofor j:=1 to n doread(fdat,datai,j);for i:=1 to n dobeginfor j:=1 to n do write(da
18、tai,j:5);writeln;end;writeln;end;procedure print;输出vari:byte;begini:=1;write(Path is:,a:2);while pathi0 dobeginwrite(pathi:2);inc(i);end;writeln;writeln(Longth=,least);end;procedure lookfor(d:integer;s:real;k:integer;already:way);求最短路径varj:byte;begin;for j:=1 to n doif (datad,j0) and not(j in alread
19、y) thenbeginpath1k:=j;if (j=b) and (s+datad,j);readln(a);write( To which);readln(b);least:=1e+36;lookfor(a,0,1,a);print;readln;end.fdat文件数据:70 2 5 3 0 0 00 0 2 0 0 7 00 0 0 1 3 5 00 0 0 0 5 0 00 0 0 0 0 1 70 0 0 0 0 0 50 0 0 0 0 0 0 例4 图5所示的网络代表6个城市间的交通网，边上权是公路的造价，现在要用公路把6个城市联系起来，这要修筑5条公路，如何设计使得这5 条
20、公路总的造价最小。 图 5分析：这是一个最小生成树问题，所谓最小生成树就是从某个顶点出发遍历图中的各点，且使各边权的总和为最小，一个网络的最小生成树不一定是唯一的。图6是图5的两个最小生成树，它们权的总和均为。图 6算法步骤：构成最小生成树的典型算法有Prime算法与Kruskal算法等。本题解答用Kruskal算法:先把平面上各顶点之间的边统统擦掉，只剩下一些孤立的点；把各边的长度按从小到大的次序排列好；按从小到大的次序把每边加到图中去，每加进去一条边，就判断一下是否产生回路？没有回路就加进去下一条边；若产生回路就放弃这条边，而考虑下一条边，碰到两条等长的边，可任取一条；重复步骤，直至加满（
21、）条边，就把个顶点连接起来了，且边长总和为最小。源程序如下：program least cost;constmax=10;typeway=set of 1.max;gradat=array1.max,1.max of real;vardata:gradat;n:byte;cost:real;already:way;k:byte;path:array1.2,1.max of byte;procedure getdata;输入数据varname:string12;fdat:text;i,j:byte;beginwrite(use which file?);readln(name);assign(f
22、dat,name);reset(fdat);read(fdat,n);for i:=1 to n dofor j:=1 to n doread(fdat,datai,j);for i:=1 to n dobeginfor j:=1 to n do write(datai,j:5);writeln;end;writeln;end;procedure print;输出vari:byte;beginfor i:=1 to n-1 dowriteln(Road side:,path1,i:3,path2,i:3);writeln(Total=,cost);end;procedure lookfor(v
23、ar n1,n2:byte);查找这一轮中的最小边vari,j:byte;m:real;beginm:=1e+36;for i:=1 to n doif i in already thenfor j:=1 to n doif (not(j in already) and (datai,j0) and (datai,jm) thenbeginm:=datai,j;n1:=i;n2:=j;end;end;procedure add;记录最小生成树及总造价vari,j:byte;beginrepeatlookfor(i,j);already:=already+j;cost:=cost+datai,j;inc(k);path1,k:=i;path2,k:=j;until already=1.n;end;begingetdata;already:=1;k:=0;cost:=0;add;print;readln;end.fdat文件数据:60 16 0 0 19 2116 0 5 6 0 110 5 0 6 0 00 6 6 0 18 1419 0 0 18 0 3321 11 0 14 33 0
