網(wǎng)上找的一些數(shù)據(jù)結(jié)構(gòu)3圖應(yīng)用

1、第三講 圖的應(yīng)用 一、圖的深度優(yōu)先遍歷的應(yīng)用 1、深度優(yōu)先訪問的特點：像樹的前序遍歷。首先訪問一個頂點Vi，并標記已經(jīng)訪問過，然后再從Vi點的一個未被訪問過的鄰接點出發(fā)，訪問下一個點，用同樣的方法，再訪問其該點的未被訪問過的鄰接點，直到訪問了所有鄰接點。在訪問的過程中，如果已經(jīng)被訪問過或無法繼續(xù)訪問，則需要退回到上一步，修改訪問的路徑（遞歸、回溯）。2、應(yīng)用例題1跳馬周游棋盤問題在nn的國際象棋上的某一位置上放置一個馬，然后采用象棋中“馬走日字”的規(guī)則，要求這個馬能不重復(fù)地走完 nn 個格子，試用計算機解決這個問題。 分析：（1）本題可以看作是圖的深度遍歷的應(yīng)用。騎士的位置為圖的一個頂點，它可

2、以移動到的其它頂點，即為圖中待訪問的頂點，該題訪問的方法不同與圖的深度優(yōu)先遍歷之處在于增加訪問的規(guī)則。（2）設(shè)騎士在某一位置，設(shè)(X,Y )，按規(guī)則走，下一步可以是如圖3-1 ( n=5 ) 所示的8個位置之一。 （3）考慮前進的方向：如果某一步可繼續(xù)走下去，就試探著走下去且考慮下一步的走法，若走不通則返回，考慮另選一個位置，其算法是： 圖3-1 procedure 試探下一步 ； begin 選擇準備； repeat 個位置中選一個；if 選擇可接受 then begin 記錄移動情況； if 棋盤未遍歷完 then begin 試探下一步； if 試探不成功 then 刪去以前的記錄 回溯

3、 end end until ( 移動成功 ) or ( 再無別的選擇 )end ； const n=8 ； nsq=64 ； type index = 1.n ； var i , j ： index ； g ： boolean ； b ： array1.n, 1.n of integer ； bi1,j1 0 當棋格 ( i1, j1 ) 未被占據(jù) i 當棋格 ( i1, j1) 在第 i 次移動中被占據(jù) （5）用數(shù)組 B 記錄移動的情況，當可以走通時則 b i1 , j1 ：=i ； 若走不通需刪除以前記錄時則 b i1 ,j1：= 0 。 （6）用 K 表示當前進行的方向，選下一個位置就

4、是改變下標值：設(shè)當前下標為 (X , Y )( U1 ,V1 ) 其關(guān)系是 U1=X-1 , V1=Y+2； ( X, Y )( U2 ,V2 ) 有關(guān)系是 U2=X-2 ,V2=Y+1 等,用坐標增量來表示移動情況。 程序如下： Program p3_1 ； const n=8 ； nsq=64 ； type index = 1.n ； var i , j ：index ； g ： boolean ； a ： array 1.2, 1.n of integer ； 棋子移動時，坐標變化 b ： array 1.n , 1.n of integer ； procedure try ( x ,

5、y ： index ； i： integer ； var q： boolean )； var k , u , v： integer ； q1 ： boolean ； begin k：=0 ； repeat k：=k+1 ； 第k 個方向（ 8個方向） q1：=false ； u：=x+a1,k ； 確定跳馬的位置 v：=y+a2 ,k ； if ( 1 = u) and ( u=8 ) and ( 1=v ) and ( v=8 ) then if bu,v=0 then begin 沒有走過的空格位 bu,v： = i ； 第i 步在 u,v 處放置棋子 if i 2 then begin

6、writeln( no solution ) ;exit ;end;Write(k); I:=1 ; 從第一個奇點出發(fā)或沒有奇點，從第一點出發(fā) While ( m2 ) do Begin Repeat I:=I+1 ; until ak,I 0 ; 找與當前點相鄰接的點 I If bI 1 then begin 修正I點 Write( ,I ) ; A k,I:=0 ;aI,k:=0 ; 對稱性 BI:=bI-1 ;bk:=bk-1 ; M:=m-2 ;k:=I; I:=0 ; End; Repeat I:=I+1 ; until ak,I0 ; 畫最后一筆 Writeln( ,I ) ;En

7、d. 二、圖的廣度優(yōu)先遍歷的應(yīng)用 1圖的廣度優(yōu)先遍歷的特點：類似樹的按層遍歷。其過程：首先訪問初始點Vi,并將其標記為已經(jīng)訪問過，接著訪問Vi的所有未被訪問過的鄰接點Vi1,Vi2, Vit,并做標記為已經(jīng)訪問過，然后再按照Vi1,Vi2, Vit，的次序，訪問每一個頂點的所有未被訪問過的鄰接點，直到圖中所有頂點都被訪問過為止。 2圖的廣度優(yōu)先遍歷，可以采用隊列方法實現(xiàn)。即訪問一個頂點，將其與它鄰接的點全部入隊，再依次訪問第二個頂點，將與它鄰接頂點入隊，直到所有頂點都被訪問過為止。 例題3四色問題。設(shè)有如圖3-3的地圖，每個區(qū)域代表一個省，區(qū)域中的數(shù)字表示省的編號，現(xiàn)在要求給每個省涂上紅、藍、

8、黃、白四種顏色之一，同時使相鄰的省份以不同的顏色區(qū)分。 圖3-3 圖3-4（1）本題是圖論中的一個搜索問題，我們可以將該問題簡化：將每個省看著一個點，而將省之間的聯(lián)系看作一條邊，可以得到如圖3-4所示圖形。（2）從圖3-3可以知道各省之間的相鄰關(guān)系，我們可以用鄰接矩陣，即用一個二維數(shù)組來表示： Rx，y = 1 表示省 x 與省 y 相鄰 0 表示省 x 與省 y 不相鄰 由圖3-3可以得到如下矩陣 1 2 3 4 5 6 710100001210111113010100040110100501010106010010171100010（3）從編號為1的省開始按四種顏色順序填色，即訪問第一個省

9、，當?shù)谝粋€省顏色與相鄰省顏色不同時，就可以確定第一個省的顏色，然后，再依次對第二、第三，進行處理，直到所有省份顏色都涂上為止。（4）問題關(guān)鍵在于在填色過程中，如果即將填的顏色與相鄰省的顏色相同，而且四種顏色都試探過，均不能滿足要求，則需要回溯到上一個點（即前一個?。薷纳弦粋€省的顏色，重新試探下一個省的顏色。Procedure 涂色過程 ； Begin 初始化工作并對第一個省涂色； While x= n do 還有省份沒有涂色 While (y= 4 ) and (x=n) do 選擇顏色 Begin If kx and ( 檢查相鄰區(qū)域，如不是當前要涂色區(qū)域 ) then 試探下一區(qū) ：

10、k+1 K If 當前顏色不能涂， then 試探下一種顏色：y+1y Else 本區(qū)域涂色，準備試探下一區(qū)域 If 試探不成功 then 回溯 x-1 x 返回上一個點（?。?修正y 顏色的值 end ； end；在上面算法中，如何檢測相鄰區(qū)域是否涂色以及涂什么顏色的計算機表示方法：S 數(shù)組表示某區(qū)域所涂的顏色，R數(shù)組表示省之間的關(guān)聯(lián)，用0，1表示，因此檢查相鄰區(qū)域是否涂色或涂的顏色是否相同用：sk*Rx,ky 表示。Program p3_3； Const max=100 ； Var R：array 1.max,1.max of 0.1 ； S：array1.max of integer ；

11、 N, a,b ：integer ； Procedure mapcolor ； Var x,y,k ：integer ； Begin S1：=1 ； x：=2 ； y：=1 ； 初始化 While x=n do While ( y=4 ) and (x=n ) do Begin K：=1 ； While (kx) and (sk*R x,k y ) do k：=k+1 ； If k4 then begin 回溯到上一個省 X：=x-1 ； Y：=sx+1 ； 修正顏色值 End ； Edn； while y End ； 過程結(jié)束 Being Write( n= )； Readln(n) ； F

12、or a：=1 to n do 輸入省之間關(guān)聯(lián) For b：=1 to n do Read(Ra,b) ； Readln ；For a：=1 to n do 輸出關(guān)聯(lián)矩陣 Begin For b：=1 to n do write(Ra,b) ； writeln ； End ； Mapcolor ； 調(diào)用涂色過程 For a：=1 to n do 輸出解 Writeln( x：5 ,：,sx：5) ；End.例題4，隊和廣度優(yōu)先搜索的運用 圖3-5表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個城市。現(xiàn)要找出一條經(jīng)過城市最少的一條路線。 用隊列的方法。用a記錄搜索過

13、程，a.city記錄經(jīng)過的城市,a.pre記錄前趨元素，這樣就可以倒推出最短線路。具體過程如下：（1） 將城市A入隊，隊首、隊尾都為1。（2） 將隊首所指的城市所有可直通的城市入隊（如果這個城市在隊中出現(xiàn)過就不入隊，可用一個集合來判斷），將入隊城市的pre指向隊首的位置。然后將隊首加1，得到新的隊首城市。重復(fù)以上步驟，直到城市H入隊為止。當搜到城市H時，搜索結(jié)束。利用pre可倒推出最少城市線路。P.42 問題二、隊列應(yīng)用 例題4 1995年高中組基礎(chǔ)題第4 題從入口（1）到出口（17）的可行路線圖中，數(shù)字標號表示關(guān)卡：現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲如下 ： 12187312419851316

14、614159170111222345681011111112 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18NOPRE 請設(shè)計一種能從存儲數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法。 （1）該題是一個路徑搜索問題，根據(jù)圖示，從入口（1）到出口（17）可以有多種途徑，其中最短的路徑只有一條，那么如何找最短路徑是問題的關(guān)鍵。（2）根據(jù)題意，用一維數(shù)組存儲各關(guān)卡號（設(shè)NO），用另一個數(shù)組存儲訪問到某關(guān)卡號的前趨關(guān)卡號（設(shè)PRE）。（3）由于本題是一個典型的圖的遍歷問題，此題可以采用圖的廣度優(yōu)先遍歷算法，并利用隊列的方式存儲頂點之間的聯(lián)系。即訪問一個點，將其

15、后繼結(jié)點入隊，并存儲它的前趨結(jié)點，直到最后從（17）點出口。（4）從最后出口的關(guān)卡號（17）開始回訪它的前趨關(guān)卡號，則回返的搜索路徑便是最短路徑。（跳過許多不必要搜索的關(guān)卡）。 （5） 從列表中可以看出出口關(guān)卡號（17）的被訪問路徑最短的是： （17） （16）（19）（18）（1）開始 const ju: array1.8,1.8 of 0.1=(1,0,0,0,1,0,1,1), (0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,

16、1,1,0), (1,1,1,1,0,0,0,1); type R=record 記錄定義 city:array1.100 of char; pre:array1.100 of integer; end;var h,d,i:integer;a: R;s: set of A.H;procedure out; 輸出過程beginwrite(a.cityd);repeatd:= a.pred;write (-,a.cityd);until a.pred=0;writeln;halt;end; procedure doit;beginh:=0; d:=1;a.city1:=A;a.pre1:=0;s:

17、=A; repeat 步驟2inc(h); 隊首加一，出隊for i:=1 to 8 do 搜索直通的城市if （ju ord(a.cityh)-64, I =0） and （not（chr（i+64） in s）then 判斷城市是否走過 begin inc(d); 隊尾加一，入隊 a.cityd:=chr(64+i); a.pred:=h; s:=s+a.cityd; if a.cityd=H then out;end;until h=d;end; begin 主程序doit;end.輸出： H-F-A 例題5 有10升油在10升的容器中，另有兩個7升和3升的空容器，現(xiàn)要求用這三個容器倒油

18、，使得最后在10升和7升的容器中各有5升油。題解 三個容器可以看作三個變量 C10，C7，C3，每次倒油的可能性只有如下六種情況： C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油 從一個容器的狀態(tài)（三個容器中油的容量）看，雖然有可能經(jīng)過上述六種倒油的方法產(chǎn)生六種容器狀態(tài)，但實際上這六種新產(chǎn)生的容器狀態(tài)，許多是已經(jīng)出現(xiàn)過的狀態(tài)。例如初始狀態(tài)（10,0,0）表示 C10=10，C7=0，C3=0，經(jīng)過上述六種倒油方法只能產(chǎn)生出兩種新的容器狀態(tài)（3,7,0），表示C10向C7倒油的結(jié)果和（7,0,3），表示C

19、10向C3倒油的結(jié)果。如果再增加應(yīng)該表示新容器狀態(tài)是由什么狀態(tài)產(chǎn)生的指示pre，那么用這三個容器倒油的過程就可以用隊列的技法來實現(xiàn)了 隊列可以理解為一個數(shù)組，數(shù)組元素是如下記錄： RECORD C10,C7,C3,pre:integer; END;數(shù)組下標為容器狀態(tài)號。下面是倒油過程的隊列圖示： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1037037646491912828507074343161607705250033300330031212300011223567891011121314151617 C10 C7 C3 PRE 當?shù)褂?/p>

20、產(chǎn)生出第19個容器狀態(tài)時已達到了題解的目的。這時只要根據(jù)pre中的狀態(tài)號17可以回溯到第17個容器狀態(tài)的pre值為15，依次可再獲得13，11，9，7，5，2，1容器狀態(tài)號，從而即可得到解題的倒油過程（共倒9次）。 請注意,從一個容器中向另一個容器中倒油,人操作是很直觀的,對編程來說則必須考慮: 1) 有沒有油可倒? 2) 究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已經(jīng)滿了. 隊列元素說明了100個,是因為10升容器最多有010種狀態(tài),7升容器最多有07種狀態(tài),3升容器最多有03種狀態(tài),全部可能的狀態(tài)為 11*8*4=352種,但油的總量為10,因此352種可能狀態(tài)中大部分

21、是不存在的.變量fp,rp在程序中用作隊列的頭指針和尾指針;flag在程序中標識是否已倒出了需要的容器狀態(tài)(C10=5,C7=5);下面是程序清單: PROCEDURE cup; BEGIN int; IF w100 THEN BEGIN IF w10+w7=7 THEN BEGIN w10:=w10-7+w7; w7:=7； END ELSE BEGIN w7:=w10+w7; w10:=0； END; push; IF (qrp.c10=5) and (qrp.c7=5) THEN BEGIN flag:=true; exit END END; int; if w100 then begi

22、n if w10+w3=3 then begin w10:=w10-3+w3; w3:=3 ； end else begin w3:=w10+w3; w10:=0 end; push; if (qrp.c10=5) and (qrp.c7=5 ） then begin flag:=true; exit end end; int; IF w70 THEN BEGIN w10:=w10+w7; w7:=0; push; IF (qrp.c10=5) and (qrp.c7=5 THEN BEGIN flag:=true; exit END END; int; IF w70 THEN BEGIN I

23、F w7+w3=3 THEN BEGIN w7:=w7-3+w3; w3:=3； END ELSE BEGIN w3:=w7+w3; w7:=0; END; push; IF (qrp.c10=5) and (qrp.c7=5 THEN BEGIN flag:=true; exit END END; int; IF w30 THEN BEGIN w10:=w10+w3; w3:=0; push; IF (qrp.c10=5) and (qrp.c7=5 THEN BEGIN flag:=true; exit END END; int; IF w30 THEN BEGIN IF w7+w3=7

24、THEN BEGIN w3:=w3-7+w7; w7:=7 END ELSE BEGIN w7:=w7+w3; w3:=0 END; push; IF w70 THEN BEGIN IF w7+w3=3 THEN BEGIN w7:=w7-3+w3; w3:=3； END ELSE BEGIN w3:=w7+w3; w7:=0; END; push; IF (qrp.c10=5) and (qrp.c7=5 THEN BEGIN flag:=true; exit END END; int; IF (qrp.c10=5) and (qrp.c7=5 THEN BEGIN flag:=true; exit END END; END; BEGIN fp:=1; rp:=1; q1.c10:=10; q1.c7:=0; q1.c3:=0; q1.pre:=0; flag:=false;repea