趣谈数据结构VIP专享VIP免费

趣谈数据结构（十） 福州一中 陈颖 本讲通过几个例子，着重讲解图的两种存储结构－－邻接表和邻接矩阵的使用，介绍图应用中常见的几种问题的处理方法及算法。 例 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. ...