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