趣谈数据结构（十）
    　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　 福州一中 陈颖

　　本讲通过几个例子，着重讲解图的两种存储结构－－邻接表和邻接矩阵的使用，介绍图应用中常见的几种问题的处理方法及算法。

　　例1 有如图1所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能有
涂色方案。
　　分析:本题实际上就是著名的"地图四色"问题。无论地图多么复杂，只需用四种颜色就可以将相邻的区域分开。
　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　图 1
　　为了解题方便，我们可以把七巧板上每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这样，该问题就转化为图的问题了。
　　算法步骤:
　　按顺序分别对１号、２号、......、７号区域进行试探性涂色，用１、２、３、４号代表４种颜色。数据采用邻接矩阵。
　　⒈对某一区域涂上与其相邻区域不同的颜色。
　　⒉若使用４种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。
　　⒊转步骤１继续涂色，直到全部结束为止，输出。
　　源程序如下:
　　program four-colors(input,output,fdat);
　　const
　　max=10;
　　type
　　gradat=array[1..max,1..max] of byte;
　　var
　　data:gradat;
　　n:byte;
　　color:array[1..max] of byte;
　　total:integer;
　　procedure getdata;{输入数据}
　　var
　　name:string[12];
　　fdat:text;
　　i,j:byte;
　　begin
　　write('use which file?');
　　readln(name);
　　assign(fdat,name);
　　reset(fdat);
　　read(fdat,n);
　　for i:=1 to n do
　　for j:=1 to n do
　　read(fdat,data[i,j]);
　　for i:=1 to n do
　　begin
　　for j:=1 to n do write(data[i,j]:5);
　　writeln;
　　end;
　　writeln;
　　end;
　　function colorsame(s:byte):boolean;{判断相邻点是否同色}
　　var
　　i:byte;
　　begin
　　colorsame:=false;
　　for i:=1 to s-1 do
　　if (data[i,s]=1) and (color[i]=color[s]) then colorsame:=true;
　　end;
　　procedure print;{输出}
　　var
　　i:byte;
　　begin
　　for i:=1 to n do write(color[i]:2);
　　inc(total);
　　writeln(' con:',total);
　　end;
　　procedure try(s:byte);{递归搜索}
　　var
　　i:byte;
　　begin
　　if s>7 then print
　　else
　　begin
　　i:=0;
　　repeat
　　inc(i);
　　color[s]:=i;
　　if not(colorsame(s)) then try(s+1);
　　until i=4
　　end;
　　end;
　　begin {主源程序如下}
　　getdata;
　　total:=0;
　　try(1);
　　writeln('Total=',total);
　　readln;
　　end.
　　fdat文件内容:
　　7
　　0 1 0 0 1 0 1
　　1 0 0 1 0 1 0
　　0 0 0 0 0 1 1
　　0 1 0 0 0 1 1
　　1 0 0 0 0 0 1
　　0 1 1 1 0 0 0
　　1 0 1 1 1 0 0

　　例2 对图2从V1点出发，沿着边系统地访问该图中其它所有的顶点一次且仅一 次。(用两种不同的解法)
　　　
　　　　　　　　　 图2　　　　　　　　　　　　　　　 图 3
　　分析:从图上某点出发，沿边访问图中其它所有的顶点一次且仅一次，称为图的遍历。图的遍历有两种方式：深度优先搜索遍历与广度优先搜索遍历。
　　算法步骤:

　　（一）深度优先搜索遍历算法
　　⒈以给定的某个顶点V0为起始点，访问该顶点；
　　⒉选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复上述过程；
　　⒊当到达一个其所有邻接的顶点都已被访问过的顶点Vi时，就退回到新近被访问过的顶点Vi-　1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程；
　　⒋直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。
　　这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。
　　图13.14中从Ｖ１出发的一种深度优先搜索访问顺序：
　　Ｖ１-->Ｖ２-->Ｖ４-->Ｖ８-->Ｖ５-->Ｖ６-->Ｖ３-->Ｖ７

　　（二）广度优先搜索遍历算法
　　⒈从图中的某一顶点V0开始，先访问V0；
　　⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；
　　⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；
　　⒋循此以往，直至所有的顶点都被访问过为止。
　　这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。
　　图13.14中，从Ｖ１出发的一种广度优先搜索访问顺序为：
　　Ｖ１-->Ｖ２-->Ｖ３-->Ｖ４-->Ｖ５-->Ｖ６-->Ｖ７-->Ｖ８
　　源程序如下:
　　源程序如下中数据采用邻接表方式表示。邻接表如图13.15所示。
　　存储邻接表数据需要三个变量，一个存储结点的内容，一个存储结点指向下一个结点的指针，一个存储每个链表的链头指针。设数组变量A(i,0)存放结点，A(i,1)存放结点的指针，Ｈ存放链头指针。
　　数据存放形式如表1所示。　
　　 　　　　　　　　　　　　　　　表1
　　　

　　源程序如下：
program bianli(input,output,fdat);
const
max=10;
type
gradat=array[1..max,1..max] of integer;
way=set of 1..max;
var
data:gradat;
n,k:byte;
path:array[1..max] of byte;
already:way;
m:integer;
procedure getdata;{输入数据}
var
name:string[12];
fdat:text;
i,j:byte;
begin
write('use which file?');
readln(name);
assign(fdat,name);
reset(fdat);
read(fdat,n);
for i:=1 to n do
begin
j:=0;
repeat
inc(j);
read(fdat,data[i,j]);
until data[i,j]=0;
end;
for i:=1 to n do
begin
j:=1;
write('[',i:2,' ]');
while data[i,j]<>0 do
begin
write(data[i,j]:3);
inc(j);
end;
writeln;
end;
end;
procedure print;{输出}
var
i:byte;
begin
for i:=1 to n do write(path[i]:2);
writeln;
end;
procedure width(s:byte);{广度优先搜索遍历}
var
useful,next:way;
i,j:byte;
begin
k:=1;
path[k]:=s;
useful:=[s];
already:=[s];
next:=[];
repeat
for i:=1 to n do
if i in useful then
begin
j:=1;
repeat
if not(data[i,j] in already) then
begin
next:=next+[data[i,j]];
already:=already+[data[i,j]];
inc(k);
path[k]:=data[i,j];
end;
inc(j)
until data[i,j]=0;
end;
useful:=next;
next:=[];
until k=n;
end;
procedure deepth(s:byte);{深度优先搜索遍历}
var
i:byte;
begin
i:=1;
inc(k);
path[k]:=s;
already:=already+[s];
while data[s,i]<>0 do
begin
if not(data[s,i] in already)
then deepth(data[s,i]);
inc(i);
end;
end;
begin
getdata;
k:=0;
already:=[];
repeat
write('Which do you want to begin:');
readln(m);
until (m>0) and (m<=n);
deepth(m);
write('Deep path is: ');
print;
width(m);
write('Wide path is: ');
print;
readln;
end.
fdat文件数据:
8
2 3 0
1 4 5 0
1 6 7 0
2 8 0
2 8 0
3 8 0
3 8 0
4 5 6 7 0

　　例3 如图4所示，从A到B有好几条可供选择的路线， 每条路线的长度均标示在图上，问选择什么样的路线，可使从A到B所走的路径最短？
　　　　　　
　　　　　　　　　　　　　　　图 4
　　分析：在一个有向图G=(V,E)中，给定一个始点V1和终点Vp，对每条弧(Vi,Vj) 相应地有一个权W(i,j)，最短路问题就是要求从始点V1到终点Vp的一条路径，使其在所有从V1到Vp的路径中，它是总权最小的一条。
　　当所有的W(i,j)>=0时，解决最短路径问题的比较好的方法是Dijkstra方法。 它是荷兰计算机科学家（E.W.Dijkstra）于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标号的点，考虑所有满足下列条件的顶点Vi的集合B:
　　B＝{ Vj|(Vi,Vj) E且Vj是T标号}
将集合B中的每一个顶点Vj的T标号修改为:
min{T(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)=min{T(V2)，P(V1)+W(1,2)}=min{+∞，2}=2
　　　T(V3)=min{T(V3)，P(V1)+W(1,3)}=min{+∞，5}=5
　　　T(V4)=min{T(V4)，P(V1)+W(1,4)}=min{+∞，3}=3
　　将其中最小者改为标号：P(2)=2

　　第二步：考虑所有与V1，V2相联且标有T标号的点集合：
　　　B={V3，V4，V6}；修改集合B中元素的T标号
　　　T(V3)=min{T(V3)，P(2)+W(2,3)}=min{5,4}=4
　　　T(V4)=3 (同前面求法)
　　　T(V6)=min{T(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)=4
　　　T(V5)=min{T(V5)，P(V4)+W(4,5)}=min{+∞，8}=8
　　　T(V6)=9
　　将其中最小者改变为P标号：P(V3)=4

　　第四步：考虑所有与V1，V2，V3，V4相联且标有T标号的点的集合：
　　　B={V5，V6}；修改集合B中的元素的T标号
　　　T(V5)=min{T(V5)，P(V3)+W(3,5)}=min{8，7}=7
　　　T(V6)=min{T(V6)，P(V3)+W(3,6)}=min{9，9}=9
　　将其中最小者改变为P标号：P(V5)=7

　　第五步：考虑所有与V1，V2，V3，V4，V5相联且标有T标号的点的集合：
　　　B={V6，V7}；修改集合B中的元素的T标号
　　　T(V6)=min{T(V6)，P(V5)+W(5,6)}=min{9，8}=8
　　　T(V7)=min{T(V7)，P(V5)+W(5,7)}=min{+∞，14}=14
　　将其中最小者改变为T标号：P(V6)=8

　　第六步：考虑所有与V1，V2，V3，V4，V5，V6相联且标有T标号的点的集合：
　　　B={V7}；修改集合中B元素的T标号
　　　T(V7)=min{T(V7)，P(V6)+W(6,7)}=min{14，13}=13
　　将其中最小者改变为P标号：P(V7)=13
　　至此，所有顶点的Ｔ标号均已改变为Ｐ标号了，说明Ｖ１到各顶点的最短路径已全部找到。

　　源程序如下：
program least way;
const
max=10;
type
gradat=array[1..max,1..max] of real;
way=set of 1..max;
var
a,b:byte;
n:byte;
data:gradat;
path,path1:array[1..max] of byte;
least:real;
k:byte;
procedure getdata;{输入数据}
var
name:string[12];
fdat:text;
i,j:byte;
begin
write('use which file?');
readln(name);
assign(fdat,name);
reset(fdat);
read(fdat,n);
for i:=1 to n do
for j:=1 to n do
read(fdat,data[i,j]);
for i:=1 to n do
begin
for j:=1 to n do write(data[i,j]:5);
writeln;
end;
writeln;
end;
procedure print;{输出}
var
i:byte;
begin
i:=1;
write('Path is:',a:2);
while path[i]<>0 do
begin
write(path[i]:2);
inc(i);
end;
writeln;
writeln('Longth=',least);
end;
procedure lookfor(d:integer;s:real;k:integer;already:way);{求最短路径}
var
j:byte;
begin;
for j:=1 to n do
if (data[d,j]<>0) and not(j in already) then
begin
path1[k]:=j;
if (j=b) and (s+data[d,j]<least) then
begin
path:=path1;
least:=s+data[d,j];
path[k+1]:=0;
end
else lookfor(j,s+data[d,j],k+1,already+[j]);
end;
end;
begin
getdata;
write('From which>');
readln(a);
write(' To which>');
readln(b);
least:=1e+36;
lookfor(a,0,1,[a]);
print;
readln;
end.
fdat文件数据:
7
0 2 5 3 0 0 0
0 0 2 0 0 7 0
0 0 0 1 3 5 0
0 0 0 0 5 0 0
0 0 0 0 0 1 7
0 0 0 0 0 0 5
0 0 0 0 0 0 0

　 例4 图5所示的网络代表6个城市间的交通网，边上权是公路的造价，现在要用公路把6个城市联系起来，这要修筑5条公路，如何设计使得这5 条公路总的造价最小。
　　　　　　　　
　 　　　　　　　　　　　图 5
　　分析：这是一个最小生成树问题，所谓最小生成树就是从某个顶点出发遍历图中的各点，且使各边权的总和为最小，一个网络的最小生成树不一定是唯一的。图6是图5的两个最小生成树，它们权的总和均为５＋１６＋１１＋６＋１８＝５６。
　　　　　　　
　　　　　　　　　　　　　　　　　　图 6
　　算法步骤：
　　构成最小生成树的典型算法有Prime算法与Kruskal算法等。本题解答用Kruskal算法:
　　⒈先把平面上各顶点之间的边统统擦掉，只剩下一些孤立的点；
　　⒉把各边的长度按从小到大的次序排列好；
　　⒊按从小到大的次序把每边加到图中去，每加进去一条边，就判断一下是否产生回路？没有回路就加进去下一条边；若产生回路就放弃这条边，而考虑下一条边，碰到两条等长的边，可任取一条；
　　⒋重复步骤３，直至加满（ｎ－１）条边，就把ｎ个顶点连接起来了，且边长总和为最小。
　　源程序如下：
program least cost;
const
max=10;
type
way=set of 1..max;
gradat=array[1..max,1..max] of real;
var
data:gradat;
n:byte;
cost:real;
already:way;
k:byte;
path:array[1..2,1..max] of byte;
procedure getdata;{输入数据}
var
name:string[12];
fdat:text;
i,j:byte;
begin
write('use which file?');
readln(name);
assign(fdat,name);
reset(fdat);
read(fdat,n);
for i:=1 to n do
for j:=1 to n do
read(fdat,data[i,j]);
for i:=1 to n do
begin
for j:=1 to n do write(data[i,j]:5);
writeln;
end;
writeln;
end;
procedure print;{输出}
var
i:byte;
begin
for i:=1 to n-1 do
writeln('Road side:',path[1,i]:3,path[2,i]:3);
writeln('Total=',cost);
end;
procedure lookfor(var n1,n2:byte);{查找这一轮中的最小边}
var
i,j:byte;
m:real;
begin
m:=1e+36;
for i:=1 to n do
if i in already then
for j:=1 to n do
if (not(j in already)) and (data[i,j]<>0) and (data[i,j]<m) then
begin
m:=data[i,j];
n1:=i;
n2:=j;
end;
end;
procedure add;{记录最小生成树及总造价}
var
i,j:byte;
begin
repeat
lookfor(i,j);
already:=already+[j];
cost:=cost+data[i,j];
inc(k);
path[1,k]:=i;
path[2,k]:=j;
until already=[1..n];
end;
begin
getdata;
already:=[1];
k:=0;
cost:=0;
add;
print;
readln;
end.
　　fdat文件数据:
6
0 16 0 0 19 21
16 0 5 6 0 11
0 5 0 6 0 0
0 6 6 0 18 14
19 0 0 18 0 33
21 11 0 14 33 0

    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有