趣谈数据结构十.docVIP

趣谈数据结构（十） 陈颖 　　例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 s7 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中从Ｖ１出发的一种深度优先有哪些信誉好的足球投注网站访问顺序：--Ｖ２--Ｖ４--Ｖ８--Ｖ５--Ｖ６--Ｖ３-