圖的基本概念存儲遍歷

圖的基本概念11、圖的的定義如果數(shù)據(jù)元素集合D中的各元素之間存在任意的前驅(qū)和后繼關(guān)系R，則此數(shù)據(jù)結(jié)構(gòu)G=（D，R）稱為圖。如果將數(shù)據(jù)元素抽象為結(jié)點，元素之間的先后關(guān)系用邊表示，則圖亦可以表示為G=（V，E），其中V是結(jié)點的有窮（非空）集合，E為邊的集合。如果元素a是元素b的前驅(qū)，這種先后關(guān)系對應(yīng)的邊用(a，b)表示，即(a，b)∈E。圖可以分為無向圖和有向圖兩種形式。22：圖結(jié)構(gòu)的基本概念（1)圖：一個圖G由兩個集合V和E組成，記為G=（V，E）。圖的數(shù)據(jù)元素通常稱為頂點（vertex），V是有限的非空頂點集，E是兩個頂點之間的關(guān)系的有限集，分別記為V（G）、E（G）。（2)有向圖：任意<x，y>∈E（G），表示從頂點x到頂點y的一條?。╝rc），且稱x為弧尾（tail）或初始點，稱y為弧頭（head）或終端點。此時E（G）中的元素是有序的（即<x，y>≠<y，x>），稱G為有向圖（digraph）。3（3）

無向圖：任意（x，y）∈E（G），表示x和y這兩個頂點之間有一條邊（edge）。此時E（G）中的元素是無序的（即（x，y）=（y，x）），稱G為無向圖（undigraph）。（4）

圖的頂點和邊的性質(zhì)1：設(shè)圖G中有n個頂點、e條邊，即n=︱V（G）︳，e=︱E（G）︳，則（1）對無向圖，0≤e≤n(n-1)/2；（2）對有向圖，0≤e≤n(n-1)。4（5）

完全圖、有向完全圖、稀疏圖、稠密圖：有n(n-1)/2條邊的無向圖稱為完全圖（completedgraph）；有n(n-1)條邊的有向圖稱為有向完全圖；邊或弧很少（如e<nlogn）的圖稱為稀疏圖（sparsegraph），反之稱為稠密圖（densegraph）。5（6）權(quán)、網(wǎng)：有時，圖的邊或弧帶有與它相關(guān)的數(shù)，叫做權(quán)（weight）或代價(cost)。這種帶權(quán)的圖通常稱為網(wǎng)（network）。（7）子圖：假設(shè)有兩個圖G=（V，E），G’=（V’，E’），若V（G）≦V’（G’）且E（G）≦E’（G’），則成G為G’的子圖（subgraph）。6（8）

鄰接點、度：對于無向圖G=（V，E），如果邊（v，v’）∈E（G）,則稱頂點v和v’互為鄰接點（adjacent），即v和v’相鄰接。邊（v，v’）依附于頂點v和v’，或者說邊（v，v’）和頂點v、v’相關(guān)聯(lián)。對于無向圖G=（V，E），v∈V（G），頂點v的度（degree）是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD（v）。對于有向圖G=（V，E），如果弧<v，v’>∈E（G），則稱頂點v鄰接到v’，頂點v’鄰接自頂點v，弧<v，v’>和頂點v、v’相關(guān)聯(lián)。對于有向圖G=（V，E），v∈V（G），以頂點v為頭的弧的數(shù)目稱為v的入度（in-degree），記為ID（v）；以v為尾的弧的數(shù)目稱為v的出度(out-degree)，記為OD（v）；頂點v的度為TD（v）=ID（v）+OD（v）。（9）圖的頂點和邊的性質(zhì)2：一個有n個頂點v1，v2，…，vn，e條邊或弧的圖，滿足如下關(guān)系：7（10）

路徑、回路、環(huán)：無向圖G=（V，E）中從頂點v到頂點v’的路徑（path）是一個頂點序列（v=vi0，vi1，…，vin=v’），其中，（vi(j-1)，vij）∈E（G），1≤j≤n。如果G是有向圖，則路徑也是有向的，頂點序列應(yīng)滿足<vi(j-1)，vij>∈E（G），1≤j≤n。路徑的長度是路徑上邊或弧的數(shù)目或它們的權(quán)之和。第1個頂點和最后1個頂點相同的路徑稱為回路或環(huán)(cycle)。序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第1個頂點和最后1個頂點相同外，其余頂點不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。（11）

連通、連通圖、連通分量：在無向圖G中，如果從頂點v到頂點v’有路徑，則稱v和v’是連通的。如果圖中任意兩個頂點之間都存在路徑，則稱該無向圖G為連通圖。連通分量指的是圖中的極大連通子圖。在有向圖G中，如果對于每一對頂點v、v’，從v到v’和從v’到v都存在路徑，則稱G是強連通圖。有向圖的極大強連通子圖稱為有向圖的強連通分量。83、圖的存儲結(jié)構(gòu)圖的鄰接矩陣表示法鄰接矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若G=（V，E）是一個具有n個結(jié)點的圖，用鄰接矩陣表示法來表示時，除了用鄰接矩陣中的n*n個元素存儲頂點間相鄰關(guān)系外，往往還需要另設(shè)一個向量存儲n個頂點的信息。因此其類型定義如下：const

vnum=…;{圖的頂點數(shù)}

type

adj=0..1;

adjmatrix=arry[1..vnum,1..vnum]ofadj;{鄰接矩陣matrix：英文（在數(shù)學(xué)中）矩陣}

graph=record

vexs:array[1..vnum]ofvextype;{頂點向量}

arcs:adjmatrix;{鄰接矩陣}

end;

9若圖中每個頂點只含一個編號i(1≤i≤vnum)，則只需一個二維數(shù)組表示圖的鄰接矩陣。此時存儲結(jié)構(gòu)可簡單說明如下：

const

vnum=…;{圖的頂點數(shù)}

type

adj=0..1;

adjmatrix=array[1..vnum,1..vnum]ofadj;end;10上圖中的圖G1和圖G2對應(yīng)的相鄰矩陣分別為：01110

10111

11010

11101

0101011鄰接表：鄰接表是順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)相結(jié)合的一種表示方法。在鄰接表中，對圖中的每一個頂點vi建立一個單鏈表li，vi作為單鏈表li的頭結(jié)點，li中的每個結(jié)點表示與這個頂點vi相關(guān)聯(lián)的頂點。若干個頭結(jié)點用順序結(jié)構(gòu)存儲，即構(gòu)成了鄰接表。結(jié)點結(jié)構(gòu)如下：

12邊結(jié)點中adjv表示與頂點vi相關(guān)聯(lián)的頂點編號，nexte是一個指針，它指向下一個與vi相關(guān)聯(lián)的頂點，edata表示這條邊的有關(guān)數(shù)據(jù)信息，如權(quán)等。頭結(jié)點中vdata表示頂點vi的頂點數(shù)據(jù)信息，如頂點名稱等，firste表示與vi相連的第一條邊。在無向圖的鄰接表中，頂點vi的度恰為第I個鏈表中結(jié)點個數(shù)：而在有向圖中，第I個鏈表中結(jié)點個數(shù)只是頂點vi的出度，為了求得入度，必須遍歷整個鏈表。

13鄰接表的描述如下：TYPElink=^enode;enode=RECORDadjv:integer;next:link;edata:edatatype;END;vexnode=RECORDvdata:vdatatype;firste:link;END;adjlist=ARRAY[1..maxvex]OFvexnode;14相鄰矩陣的特點

⑴無向圖的相鄰矩陣是對稱的，而有向圖則不是。無向圖的相鄰矩陣a1[i，j]=a1[j，i](1≤i，j≤n)且對角線上的a[i，i]均為0（或±∝）。正因為如此，在實際存儲相鄰矩陣時只需存儲其上三角(或下三角)的元素。因此具有n個結(jié)點的無向圖，其相鄰矩陣的存儲容量可節(jié)約至n(n-1)/2。而有向圖的相鄰矩陣中a2[i，j]不一定與a2[j，i](1≤i，j≤n)相同，且圖中出現(xiàn)自反邊時其對角線上的a2[i，i]也不一定是0（或±∝）。占用的存儲單元數(shù)只與結(jié)點數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝）當(dāng)然是無端浪費。15⑵相鄰矩陣方便度數(shù)的計算。用相鄰矩陣表示圖，容易判定任意兩個結(jié)點之間是否有邊相聯(lián)，并容易求得各個結(jié)點的度數(shù)。對于無權(quán)無向圖的相鄰矩陣，第i行元素值的和就是Vi的度數(shù)；對于有權(quán)無向圖的相鄰矩陣，第i行（或第i列）中元素值<>±∝的元素個數(shù)就是Vi的度數(shù)；對于無權(quán)有向圖的相鄰矩陣，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；對于有權(quán)有向圖的相鄰矩陣，第i行中元素值<>±∝的元素個數(shù)就是Vi的出度；第i列元素值<>±∝的元素個數(shù)就是Vi的入度。16⑶容易計算路徑的存在性。在無權(quán)有向圖或無向圖中，判定兩個結(jié)點Vi、Vj之間是否存在長度為m的路徑，只要考慮am=a*a*……*a（m個a矩陣相乘后的乘積矩陣）中（i，j）的元素值是否為0就行了。(4)占用的存儲單元數(shù)只與結(jié)點數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝

）當(dāng)然是無端浪費。(5)存儲相鄰矩陣的靜態(tài)數(shù)據(jù)區(qū)僅有64kb可用空間。一旦圖的存儲容量超過了64kb，則非得采用動態(tài)數(shù)據(jù)類型的鄰接表不可。17圖的鄰接表表示法

用鄰接表法表示圖需要保存一個順序存儲的結(jié)點表和n個邊表（每個邊表為一個單鏈表，存儲與一個結(jié)點相連的所有邊的信息）。結(jié)點表的每個表目對應(yīng)于圖的一個結(jié)點，包括：

⑴結(jié)點信息，即與該結(jié)點相連的邊數(shù)（m）；訪問標(biāo)志（visited）；

⑵邊表的首指針（firstarc）。圖中每個結(jié)點都有一個邊表，其中每一個結(jié)點對應(yīng)于與該結(jié)點相關(guān)聯(lián)的一條邊，包括與此邊相關(guān)聯(lián)的另一個結(jié)點序號（v）；若為帶權(quán)圖的話，該邊的權(quán)值（w）指向邊表的下一個結(jié)點的后繼指針（nextarc）；18鄰接表的定義如下：

constmax=圖的結(jié)點數(shù)上限；Typearcptr=↑arcnode；{邊表的指針類型}arcnode=record{邊表的結(jié)點類型}v：integer；{關(guān)聯(lián)該邊的另一端點序號}nextar：arcptr；{邊表的后繼指針}w：real;{該邊的權(quán)值}end；vexnode=record{結(jié)點表的表目類型}m：integer；{與該結(jié)點相連的邊數(shù)}visited：boolean；{訪問標(biāo)志}firstarc：arcptr；{邊表的首指針}end；adjlist=array[1‥max]ofvexnode；{鄰接表類型}vardig：adjlist；{鄰接表}n，e：integer；{結(jié)點數(shù)和邊數(shù)}

19特點：（1）用鄰接表表示法來存儲圖，則占用的存儲單元既與圖的結(jié)點數(shù)有關(guān)，又與邊數(shù)有關(guān)。同樣是n個結(jié)點的圖，如果邊數(shù)少，則占用的存儲單元也少。（2）由于所有了動態(tài)變量，因此可按照實際需要所有內(nèi)存，而且用戶空間擴大至640kb（3）因為與一個結(jié)點相關(guān)聯(lián)的所有邊都鏈接在同一個邊表里，給運算提供了方便。

204.圖的建立（1）建立帶權(quán)無向圖的鄰接矩陣Constmax=maxlongint;n=10;typegraph=array[1..n,1..n]oflongint;VarI,j,k:integer;g:graph;w:longint;21ForI:=1tondoforj:=1tondog[I,j]:=max;Read(e);{讀入邊數(shù)}Fork:=1toedobeginread(I,j,w);g[I,j]:=w;g[j,i]:=w;End;ForI:=1tondoforj:=1tondowriteln(g[I,j]);End.22(2)建立有向圖的鄰接表Procedurecreatelist(varg:adjlist);BeginRead(n,e);ForI:=1tondobeginread(g[i].v);g[i].link:=nil;End;23Fork:=1toedobeginread(I,j);new(s);s^.adjv:=jS^.next:=g[i].link;g[i].link:=s;End;End;245、圖的遍歷給出一個圖G和其中任意一個結(jié)點V0，從V0出發(fā)系統(tǒng)地訪問G中所有結(jié)點，每一個結(jié)點被訪問一次，這就叫圖的遍歷。

通常有兩種遍歷方法：⑴深度優(yōu)先搜索dfs⑵廣度優(yōu)先搜索bfs它們對無向圖和有向圖都適用。我們以相鄰矩陣存儲結(jié)構(gòu)給出深度優(yōu)先搜索和廣度優(yōu)先搜索的程序。258、深度優(yōu)先搜索DFS（觀看動畫）深度優(yōu)先搜索類似于樹的前序遍歷，是樹的前序遍歷的推廣。其搜索過程如下：假設(shè)初始時所有結(jié)點未曾被訪問。深度優(yōu)先搜索從某個結(jié)點V0出發(fā)，訪問此結(jié)點。然后依次從V0的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V0有路徑相連的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未被訪問，則另選一個未曾訪問的結(jié)點作起始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問為止。換句話說，深度優(yōu)先搜索遍歷圖的過程是以V0為起始點，由左而右，依次訪問由V0出發(fā)的每條路徑。26遍歷算法：

1)從某一頂點出發(fā)開始訪問,被訪問的頂點作相應(yīng)的標(biāo)記,輸出訪問頂點號.2)從被訪問的頂點出發(fā),搜索與該頂點有邊的關(guān)聯(lián)的某個未被訪問的鄰接點再從該鄰接點出發(fā)進一步搜索與該頂點有邊的關(guān)聯(lián)的某個未被訪問的鄰接點,直到全部接點訪問完畢.如圖從V1開始的深度優(yōu)先遍歷序列為V1，V2，V3，V4，V5。算法過程：procedureshendu(i);begin

write(i);

v[i]:=true;

forj:=1tondo

if(a[i,j]=1)andnot(v[j])thenshendu(j);end;279、廣度優(yōu)先搜索(寬度優(yōu)先搜索）BFS（觀看動畫）廣度優(yōu)先搜索類似于樹的按層次遍歷的過程，其搜索過程如下：假設(shè)從圖中某結(jié)點v0出發(fā)，在訪問了v0之后依次訪問v0的各個未曾訪問的鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未被訪問，則任選其中的一個作起始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問到為止。換句話說，按廣度優(yōu)先順序搜索遍歷圖的過程是以v0為起始點，由近及遠，依次訪問和v0有路徑相連且路徑長度為1，2，3……的結(jié)點。28遍歷算法：1）從某個頂點出發(fā)開始訪問，被訪問的頂點作相應(yīng)的標(biāo)記，并輸出訪問頂點號；2）從被訪問的頂點出發(fā)，依次搜索與該頂點有邊的關(guān)聯(lián)的所有未被訪問的鄰接點，并作相應(yīng)的標(biāo)記。3）再依次根據(jù)2）中所有被訪問的鄰接點，訪問與這些鄰接點相關(guān)的所有未被訪問的鄰接點，直到所有頂點被訪問為止。如圖3的廣度優(yōu)先遍歷序列為C1,C2,C3,C4,C5,C6。29算法過程：procedureguangdu(i);

begin

write(i);

v[i]:=true;

i進隊;

repeat

隊首元素出隊設(shè)為k

forj:=1tondo

if(a[k,j]=1)and(notv[j])then

begin

write(j);

v[j]:=true;

j進隊;

end;

until隊列q為空;30當(dāng)堂練習(xí)1.

在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的__________倍。A．1/2B.1C.2D.42.

在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的__________倍。A．1/2B.1C.2D.4313.

一個有n個頂點的無向圖最多有________條邊。A．nB.n(n-1)C.n(n-1)/2D.2n4.

具有4個頂點的無向完全圖有_________條邊。A.6B.12C.16D.20

325.

具有6個頂點的無向圖至少應(yīng)有_______條邊才能確保是一個連通圖。A．5B.6C.7D.86.

在一個具有n個頂點的無向圖中，要連通全部頂點至少需要____________條邊。A．nB.n+1C.n-1D.n/2337.

對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_________。A．nB.(n-1)2C.n-1D.n28.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_______；所有鄰接表中的結(jié)點總數(shù)是___________。

A．nB.n+1C.n-1D.n+eA．eB.2eC.e/2D.n+e34上機練習(xí)題：寫出圖的深度優(yōu)先搜索(DFS)算法和廣度優(yōu)先搜索(BFS)算法。programdfsbfs(input,output);constn=8;vara:array[1..n,1..n]ofinteger;{圖的鄰接矩陣}visited,come:array[1..n]ofinteger;{訪問標(biāo)志}queue:array[1..n]ofinteger;{隊列}t:array[1..n]ofchar;{結(jié)點信息}i,head,tail:integer;35procedureinit;vari,j,e,k:integer;beginfori:=1tondoread(t[i]);{頂點信息}fillchar(a,sizeof(a),0);read(e);{邊數(shù)}fork:=1toedo{讀入邊的點信息,建立鄰接矩陣}beginread(i,j);a[i,j]:=1;a[j,i]:=1;end;end;36proceduredfs(i:integer);varj:integer;beginwrite(t[i]);{輸出結(jié)點信息}visited[i]:=1;{訪問標(biāo)志}forj:=1tondo{深度優(yōu)先搜索i的鄰接點}if(a[i,j]=1)and(visited[j]=0)thendfs(j);end;37Beginwriteln;init;fori:=1tondovisited[i]:=0;fori:=1tondoifvisited[i]=0thendfs(i);writeln;head:=0;tail:=0;fori:=1tondovisited[i]:=0;fori:=1tondoifvisited[i]=0thenbfs(i);end.38

procedurebfs(i:integer);{廣搜}varj:integer;beginwrite(t[i]);visited[i]:=1;tail:=tail+1;{尾指針加1}queue[tail]:=i;{入隊列}whilehead<=taildo{隊列非空}beginforj:=1tondo{搜索i的所有鄰接點,如果沒訪問,入隊列}if(a[queue[head],j]=1)and(visited[j]=0)thenbeginwrite(t[j]);visited[j]:=1;tail:=tail+1;queue[tail]:=j;end;head:=head+1;{出隊列,訪問隊首元素}end;end;39例題1、計算有向圖頂點的入度和出度輸入：頂點數(shù)n和邊數(shù)m以下m行，每行為一條有向邊的兩個端點輸出：共n行，其中第I行為頂點I的入度和出度40算法分析設(shè)d[i,1]和d[i,2]為頂點I的入度和出度。顯然，每讀入一條有向邊（i,j），則頂點I的出度+1（inc(d[i,2])）頂點j的入度+1（inc(d[j,1])）。由此得出readln(n,m);{讀頂點數(shù)和邊數(shù)}fillchar(d,sizeof(d),0);fori:=1tomdo{輸入每條邊，計算兩個端點的入度和出度}beginreadln(a,b);inc(d[a,2]);inc(d[b,1])end;fori:=1tondowriteln(i,':',d[i,1],'',d[i,2]);{輸出每個頂點的入度和出度}writeln41例題2、計算無向圖的所有連通分支

輸入無向圖G，計算和輸出G的所有連通分支，G的每一個頂點僅在一個連通分支上。輸入：

頂點數(shù)n和邊數(shù)e以下為e行，每行為一條無向邊的兩個端點輸出：

若干行，每行為一條連通分支

42算法分析

設(shè)constmax=100;{頂點數(shù)的上限}varn,e,i,a,b:integer;{頂點數(shù)n和邊數(shù)e}g:array[1..max,1..max]ofboolean;{無向圖}vt:array[1..max]ofboolean;{頂點的訪問標(biāo)志}1、

431、遞歸計算一個頂點所在的連通分支首先，該頂點計入連通分支，并設(shè)定其訪問標(biāo)志。然后遞歸搜索與該頂點相連的每一條未訪問邊（即該邊的另一個端點未訪問）。

proceduresearch(nw:integer);{遞歸計算nw頂點所在的連通分支}vari:integer;beginwrite(f0,nw,'');vt[nw]:=true;{輸出nw并設(shè)置nw訪問標(biāo)志}fori:=1tondo{遞歸訪問與nw相連的每一條未訪問邊}ifg[nw,i]andnotvt[i]thensearch(i)end;442、主程序有了search(i)過程便不難得出主程序：輸入無向圖的信息。然后依次對每一個未訪問的頂點執(zhí)行search過程，遞歸計算該頂點所在的連通分支，并將連通分支上的所有頂點設(shè)訪問標(biāo)志。

readln(f,n,e);{輸入頂點數(shù)n和邊數(shù)e}fillchar(g,sizeof(g),0);{有向圖初始化}fori:=1toedo{輸入有向圖的信息}beginreadln(f,a,b);g[a,b]:=true;g[b,a]:=trueend;fillchar(vt,sizeof(vt),0);{訪問標(biāo)志初始化}fori:=1tondo{搜索每一個未訪問的頂點}ifnotvt[i]thenbeginsearch(i);writeln；end;{遞歸計算I頂點所在的連通分支}

45兩道簡單的搜索題例1:有A，B，C，D，E5本書，要分給張、王、劉、趙、錢5位同學(xué)，每人只選一本。每人將喜愛的書填寫下表，輸出每人都滿意的分書方案。46用遞歸方式

47程序如下:programallotbook;

typefive=1..5;

constlike:array[five,five]of0..1=

((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));

name:array[five]ofstring[5]=('zhang','wang','liu','zhao','qian');

varbook:array[five]offive;

flag:setoffive;

c:integer;

procedureprint;

vari:integer;

begin

inc(c);

writeln('answer',c,':');

48fori:=1to5do

writeln(name[i]:10,':',chr(64+book[i]));

end;

proceduretry(i:integer);

varj:integer;

begin

forj:=1to5do

ifnot(jinflag)and(like[i,j]>0)then

beginflag:=flag+[j];

book[i]:=j;

ifi=5thenprintelsetry(i+1);

flag:=flag-[j];

end

end;

begin

flag:=[];

c:=0;

try(1);

readln;

end.49用非遞歸方法

50編程如下:programallotbook;

typefive=1..5;

constlike:array[five,five]of0..1=

((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));

name:array[five]ofstring[5]=('zhang','wang','liu','zhao','qian');

varbook:array[five]offive;

flag:setoffive;

c,dep,r:integer;

p:boolean;

procedureprint;

vari:integer;

begin

inc(c);

writeln('answer',c,':');

51

fori:=1to5do

writeln(name[i]:10,':',chr(64+book[i]));

end;

begin

flag:=[];

c:=0;dep:=0;

repeat

dep:=dep+1;

r:=0;

p:=false;

repeat

r:=r+1;

ifnot(rinflag)and(like[dep,r]>0)then

begin

flag:=flag+[r];

book[dep]:=r;

ifdep=5thenprintelsep:=true

end

52elseifr>=5then

begin

dep:=dep-1;

ifdep=0thenp:=trueelsebeginr:=book[dep];flag:=flag-[r]end;

endelsep:=false;

untilp=true;

untildep=0;

readln;

end.53例2:中國象棋棋盤如下圖馬自左下角往右上角跳.規(guī)定只許往左跳,不許往右跳(如圖跳法)編程找出所有跳法。54遞歸算法如下：programtiaoma;const

di:array[1..4]ofinteger=(1,2,2,1);

dj:array[1..4]ofinteger=(