圖及其應(yīng)用一

圖及其應(yīng)用一第一頁，共八十頁，2022年，8月28日

一、圖的基本概念1、圖的的定義

圖是由頂點(diǎn)V的集合和邊E的集合組成的二元組：記G=（V，E）第二頁，共八十頁，2022年，8月28日2、無向圖和有向圖

⑴無向圖：

在圖G=（V，E）中，如果對(duì)于任意的a，b∈V，當(dāng)(a，b)∈E時(shí)，必有（b，a）∈E（即關(guān)系R對(duì)稱），對(duì)稱圖為無向圖。在一無向圖中用不帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的頂點(diǎn)。

V={V1,V2,V3,V4,V5}

E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)}

第三頁，共八十頁，2022年，8月28日⑵有向圖：如果對(duì)于任意的a，b∈V，當(dāng)(a，b)∈E時(shí)，(b，a)∈E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。V={V1,V2,V3,V4}E={<V1,V2>,<V2,V4>,<V1,V3>,<V3,V4>,<V4,V1>}第四頁，共八十頁，2022年，8月28日頂點(diǎn)的度：無向圖：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。有向圖：等于該頂點(diǎn)的入度與出度之和。

入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和

出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和

度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。

3、頂點(diǎn)的度第五頁，共八十頁，2022年，8月28日練習(xí)題:1.假設(shè)我們用d=(a1,a2,...,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d值合理（）。

A）{5，4，4，3，1}B）{4，2，2，1，1}C）{3，3，3，2，2}D）{5，4，3，2，1}E）{2，2，2，2，2}2.無向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少_______個(gè)頂點(diǎn)。第六頁，共八十頁，2022年，8月28日4、

路徑和連通集在圖G=（V，E）中，如果對(duì)于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1……xk(k>1)

⑴x1=a，xk=b

⑵(xi，xi+1)∈Ei=1‥k-1則稱結(jié)點(diǎn)序列x1=a，x2，…，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條路徑，而路徑上邊的數(shù)目k-1（或者沿路徑各邊權(quán)值之和）稱為該路徑的長度，并稱結(jié)點(diǎn)集合{x1，…，xk}為連通集。{V1,v2,v5,v4}第七頁，共八十頁，2022年，8月28日5、簡單路徑和回路如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡單路徑。圖(a)中v1→v2→v3是一條簡單路徑，v1→v3→v4→v1→v3不是簡單路徑。x1=xk的簡單路徑稱為回路（也稱為環(huán)）。例如圖(b)中，v1→v2→v1為一條回路。第八頁，共八十頁，2022年，8月28日例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，3，1第九頁，共八十頁，2022年，8月28日二、圖的存儲(chǔ)結(jié)構(gòu)（教材P79）圖的鄰接矩陣表示法鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n1(或權(quán)值)

表示頂點(diǎn)i和頂點(diǎn)j有邊(i和j的路程)A[i][j]=

0（或∞）表示頂點(diǎn)i和頂點(diǎn)j無邊二維數(shù)組的行、列號(hào)表示頂點(diǎn)編號(hào)第十頁，共八十頁，2022年，8月28日上圖中的圖G1和圖G2對(duì)應(yīng)的相鄰矩陣分別為：無向帶權(quán)圖的鄰接(代價(jià))矩陣表示有向無權(quán)圖的鄰接矩陣表示第十一頁，共八十頁，2022年，8月28日鄰接矩陣的特點(diǎn)：1)無向圖的鄰接矩陣是對(duì)稱的，而有向圖則不是。2)鄰接矩陣方便度數(shù)的計(jì)算。用鄰接矩陣表示圖:

(1)容易判定任意兩個(gè)結(jié)點(diǎn)之間是否有邊相聯(lián);

(2)容易求得各個(gè)結(jié)點(diǎn)的度數(shù)。

對(duì)于無權(quán)無向圖的鄰接矩陣，第i行元素值的和就是Vi的度數(shù)；對(duì)于無權(quán)有向圖的鄰接矩陣，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；

對(duì)于有權(quán)無向圖的鄰接矩陣，第i行（或第i列）中元素值<>0的元素個(gè)數(shù)就是Vi的度數(shù)；對(duì)于有權(quán)有向圖的鄰接矩陣，第i行中元素值<>0的元素個(gè)數(shù)就是Vi的出度；第i列元素值<>0的元素個(gè)數(shù)就是Vi的入度。第十二頁，共八十頁，2022年，8月28日例1452375318642各頂點(diǎn)的度是多少？úúúúúúú?ùêêêêêêê?é0618360240120078400530750第十三頁，共八十頁，2022年，8月28日讀入數(shù)據(jù)構(gòu)造鄰接矩陣（P80）競(jìng)賽題中一般圖的數(shù)據(jù)是以這種方式給出的：題中會(huì)指定頂點(diǎn)數(shù)的最大值，以便于定義一個(gè)全局二維數(shù)組作為鄰接矩陣數(shù)據(jù)文件的第1行一般是圖的頂點(diǎn)個(gè)數(shù)N以及邊數(shù)M接下來一般有M行，每行有2個(gè)或3個(gè)整數(shù)，描述了每條邊的信息：如果是2個(gè)整數(shù)i，j，則一般表示頂點(diǎn)i和頂點(diǎn)j有一條邊相連如果是3個(gè)整數(shù)i，j，k，則一般表示頂點(diǎn)i和頂點(diǎn)j相連的權(quán)值為k針對(duì)圖數(shù)據(jù)的這種結(jié)構(gòu)，我們會(huì)用如下的代碼來構(gòu)造鄰接矩陣：第十四頁，共八十頁，2022年，8月28日constintMAXN=201;//最大頂點(diǎn)數(shù)inta[MAXN][MAXN],n,m,i,j,k,x;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){//讀入m條邊

scanf("%d%d",&j,&k); a[j][k]=1;//若是有向圖，則只賦值a[j][k] a[k][j]=1;//若是無向圖，則一定要賦值a[k][j]}如果是構(gòu)造帶權(quán)圖，則上述for語句中的代碼改為：

scanf("%d%d",&j,&k,&x); a[j][k]=x;//若是有向圖，則只賦值a[j][k] a[k][jl=x;//若是無向圖，則一定要賦值a[k][j]第十五頁，共八十頁，2022年，8月28日鄰接矩陣主對(duì)角線元素的處理在競(jìng)賽中很少有圖數(shù)據(jù)是頂點(diǎn)帶自環(huán)邊的，因此鄰接矩陣的主對(duì)角線元素a[i][i](1<=i<=n)一般都是0。在前面講的鄰接矩陣的構(gòu)造方法中，如果頂點(diǎn)i，j之間沒有邊，則a[i][j]也表示為0。在大多數(shù)圖的算法中，不區(qū)別這兩種值為0的情況是可以的。而在某些圖算法中，必須要區(qū)別主對(duì)角線元素和其它非主對(duì)角線元素，這時(shí)就用另外的特殊值來表示無邊相連的情況。特殊值一般取一個(gè)很大的正數(shù)（或負(fù)數(shù)），實(shí)現(xiàn)實(shí)現(xiàn)代碼如下：第十六頁，共八十頁，2022年，8月28日constintBIG=99999999;//表示無窮大for(i=1;i<=n;i++)//初始化{ for(j=1;j<=n;j++) a[i][j]=BIG; a[i][i]=0;}for(i=1;i<=m;i++){//讀入邊數(shù)據(jù)

scanf("%d%d%d",&j,&k,&x); a[j][k]=x; a[k][j]=x;//這句無向圖才要}鄰接矩陣的優(yōu)缺點(diǎn)見教材P80判斷i，j有無邊相連：O(1)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(n)空間復(fù)雜性高：O(n^2)第十七頁，共八十頁，2022年，8月28日邊集數(shù)組表示法（教材P80）一個(gè)一維數(shù)組存儲(chǔ)圖每個(gè)元素表示一條邊：起點(diǎn)、終點(diǎn)、權(quán)值（如果有的話）適用于：對(duì)邊進(jìn)行依次處理的算法，適合存儲(chǔ)頂點(diǎn)多但邊很少的稀疏圖缺點(diǎn)：判斷i，j有無邊相連：O(E)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(E)優(yōu)點(diǎn)：結(jié)構(gòu)簡單第十八頁，共八十頁，2022年，8月28日邊集數(shù)組表示法的實(shí)現(xiàn)constintMAXEDGE=2000;structnode{ ints,t;//邊的起點(diǎn)和終點(diǎn)

intw;//邊的權(quán)值}nodeedge[MAXEDGE];intn,m,i,j,k,x;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){ scanf("%d%d%d",&j,&k,&x); edge[i].s=j; edge[i].t=k; edge[i].w=x;}第十九頁，共八十頁，2022年，8月28日鄰接表表示法（P81）鄰接表表示法是指對(duì)圖中的每個(gè)頂點(diǎn)Vi(1<=i<=n)建立一個(gè)鄰接關(guān)系的單鏈表，并把它們的表頭指針用一維數(shù)組存儲(chǔ)起來的一種表示方法。為每個(gè)頂點(diǎn)Vi建立的單鏈表，是表示以該頂點(diǎn)為起點(diǎn)的所有邊的信息。以下圖（教材圖5－2）為例，頂點(diǎn)v1與v2、v3、v5相鄰，因此在v1的單鏈表里就包含3條邊的信息。v1v2v3v4v5524101183253853^頂點(diǎn)v1的單鏈表有3個(gè)結(jié)點(diǎn)，表示有3條邊與v1相接，有3個(gè)頂點(diǎn)（v2、v3、v5）是v1的鄰接點(diǎn)不表示v2與v3相鄰，v3與v5相鄰第二十頁，共八十頁，2022年，8月28日鄰接表表示法（P81）一維指針數(shù)組存儲(chǔ)了每個(gè)頂點(diǎn)的單鏈表的頭指針。一般就用數(shù)組下標(biāo)表示了起點(diǎn)編號(hào)。例如v1單鏈表的頭指針就存儲(chǔ)在adj[1]中。下圖的完整鄰接表如下所示：v1v2v3v4v5524101183253853^153256^182254^310511^1326511^4103412345第二十一頁，共八十頁，2022年，8月28日鄰接表的數(shù)據(jù)結(jié)構(gòu)constintMAXV=201;//最大頂點(diǎn)數(shù)structnode{intv;//鄰接點(diǎn)序號(hào)

intwt;//權(quán)值，如果是帶權(quán)圖的話

node*next;//鄰接單鏈表指針};node*adj[MAXV];//每個(gè)頂點(diǎn)建一個(gè)單鏈表構(gòu)造鄰接表intn,m;//n表示讀入的頂點(diǎn)個(gè)數(shù)，m表示讀入的邊條數(shù)第二十二頁，共八十頁，2022年，8月28日創(chuàng)建鄰接表voidcreatelist()//創(chuàng)建鄰接表{inti,j,k,x;node*p;scanf("%d%d",&n,&m);//讀入頂點(diǎn)數(shù)和邊數(shù)

for(i=1;i<=n;i++)//初始化每個(gè)頂點(diǎn)的邊表為NULLadj[i]=NULL;for(i=1;i<=m;i++)｛//讀入邊信息，構(gòu)造鄰接表

scanf("%d%d%d",&j,&k,&x);//讀入一條邊的起點(diǎn)，終點(diǎn)和權(quán)值

p=newnode;//申請(qǐng)一個(gè)節(jié)點(diǎn)

p->v=k;//j的鄰接點(diǎn)是kp->wt=x;//邊的權(quán)值是xp->next=adj[j];//新節(jié)點(diǎn)插在頂點(diǎn)j的邊表的表頭位置

adj[j]=p;//以下是無向圖需要構(gòu)造的對(duì)稱邊<k,j>p=newnode;p->v=j;//k的鄰接點(diǎn)是jp->wt=x;p->next=adj[k];//新節(jié)點(diǎn)插在頂點(diǎn)k的邊表的表頭位置

adj[k]=p;}}第二十三頁，共八十頁，2022年，8月28日鄰接表的優(yōu)缺點(diǎn)（P82）便于查找后繼頂點(diǎn)、以該點(diǎn)為起點(diǎn)的邊、出度。不便于查找前趨頂點(diǎn)、以該點(diǎn)為終點(diǎn)的邊、入度。解決辦法：建立逆鄰接表，即把以某頂點(diǎn)為終點(diǎn)的頂點(diǎn)放在一個(gè)單鏈表中。和鄰接矩陣相比，構(gòu)造鄰接表的編程復(fù)雜性要高一些，但是查找后繼頂點(diǎn)的效率要高O(e/n)vs.O(n)。如果邊比較稀疏，顯然用鄰接表存儲(chǔ)圖比較好。第二十四頁，共八十頁，2022年，8月28日編程練習(xí)求一個(gè)有向圖中指定頂點(diǎn)的出度。輸入數(shù)據(jù)：第1行：2個(gè)空格分開的整數(shù)n(2<=n<=200)和m(10<=m<=20000)，分別表示圖的頂點(diǎn)數(shù)和邊數(shù)。第2..m+1行：每行2個(gè)空格分開的整數(shù)i，j，i表示一條邊的起點(diǎn)，j表示終點(diǎn)。第m＋2行：1個(gè)整數(shù)k(2<=k<=n),表示指定的頂點(diǎn)。輸出數(shù)據(jù)：第1行：1個(gè)整數(shù)od，表示頂點(diǎn)k的出度。要求：分別用鄰接矩陣和鄰接表存儲(chǔ)圖。第二十五頁，共八十頁，2022年，8月28日三、圖的遍歷給出一個(gè)圖G和其中任意一個(gè)結(jié)點(diǎn)V，從V出發(fā)訪問G中所有結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)被訪問一次（不是只經(jīng)過一次），這就叫圖的遍歷。

通常有兩種遍歷方法：

⑴深度優(yōu)先搜索dfs⑵廣度優(yōu)先搜索bfs

第二十六頁，共八十頁，2022年，8月28日1、深度優(yōu)先搜索DFS方法：從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)；然后依次從V1的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V1相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。為了避免重復(fù)訪問某個(gè)頂點(diǎn)，設(shè)一個(gè)標(biāo)志數(shù)組visit，頂點(diǎn)i未訪問時(shí)，visit[i]的值為false，訪問后就改為true。V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7可以從任一頂點(diǎn)出發(fā)進(jìn)行DFS第二十七頁，共八十頁，2022年，8月28日V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7第二十八頁，共八十頁，2022年，8月28日V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V5第二十九頁，共八十頁，2022年，8月28日在程序中實(shí)現(xiàn)深度優(yōu)先搜索算法:從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)；然后依次從V1的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V1相通的頂點(diǎn)都被訪問到。如何判別V的鄰接點(diǎn)是否被訪問？解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志visit[i]”如果圖不連通，則一次DFS只能訪問所有與V1連通的頂點(diǎn)。要對(duì)整個(gè)圖進(jìn)行遍歷，則需要再任找一個(gè)尚未訪問的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問為止。第三十頁，共八十頁，2022年，8月28日abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:例如:achdkfe第三十一頁，共八十頁，2022年，8月28日參考代碼//從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索,鄰接表實(shí)現(xiàn)//適用于有向圖和無向圖voiddfs(inti){node*p;cout<<i;//輸出，最簡單的訪問

visit[i]=true;//置訪問標(biāo)志

p=adj[i];//取出鄰接表頭指針

while(p!=NULL)//依次對(duì)鄰接點(diǎn)進(jìn)行DFS{if(visit[p->v]==false)//如果鄰接點(diǎn)未訪問

dfs(p->v);//則對(duì)其遞歸DFSp=p->next;//取下一個(gè)鄰接點(diǎn)

}}第三十二頁，共八十頁，2022年，8月28日參考代碼voiddfstravel()//對(duì)圖進(jìn)行深度優(yōu)先遍歷{inti;memset(visit,0,sizeof(visit));//清訪問標(biāo)志

for(i=1;i<=n;i++)if(!visit[i])dfs(i);}第三十三頁，共八十頁，2022年，8月28日DFS的應(yīng)用1、犯罪團(tuán)伙

警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)。有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n。輸入：第一行：n（<=5000,罪犯數(shù)量），m（<50000，關(guān)系數(shù)量）以下m行：每行兩個(gè)數(shù)：i和j，中間一個(gè)空格隔開，表示罪犯i和罪犯j相互認(rèn)識(shí)。輸出：一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。第三十四頁，共八十頁，2022年，8月28日樣例輸入：118124354135671051089輸出：3說明：共三個(gè)犯罪團(tuán)伙。第三十五頁，共八十頁，2022年，8月28日分析把人處理成頂點(diǎn)，把認(rèn)識(shí)關(guān)系處理成邊，犯罪團(tuán)伙構(gòu)成一個(gè)圖（有向還是無向？）則根據(jù)輸入數(shù)據(jù)可以構(gòu)造一個(gè)鄰接表（可以用鄰接矩陣嗎？如果不能請(qǐng)說明原因）。從1到n枚舉頂點(diǎn)Vi，從Vi進(jìn)行DFS，則能找到一個(gè)團(tuán)伙。然后再另選一個(gè)未訪問的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問。最后，調(diào)用DFS的次數(shù)就是團(tuán)伙的個(gè)數(shù)。第三十六頁，共八十頁，2022年，8月28日constmaxn=1000;vara:array[1..maxn,1..maxn]oflongint;visited:array[1..maxn]of0..1;t:array[1..maxn]ofchar;n,m,i,s:longint;procedureinit;vari,x,y:longint;beginassign(input,'group5.in');reset(input);readln(n);readln(m);fori:=1tomdobeginreadln(x,y);a[x,y]:=1;a[y,x]:=1;end;close(input);end;proceduredfs(i:longint);varj:longint;beginvisited[i]:=1;forj:=1tondoif(a[i,j]=1)and(visited[j]=0)thendfs(j);end;Begininit;s:=0;fori:=1tondovisited[i]:=0;fori:=1tondoifvisited[i]=0thenbegindfs(i);inc(s);end;writeln(s);end.第三十七頁，共八十頁，2022年，8月28日12354672、哈密頓路郵遞員在送信時(shí)，為了節(jié)省路途，自己規(guī)定：每次總是從n個(gè)村子中選擇其中一個(gè)合適的村子出發(fā)，途經(jīng)每個(gè)村子僅且經(jīng)過一次，送完所有的信。已知各個(gè)村子的道路連通情況。請(qǐng)你幫郵遞員選擇一條合適的路線。輸入：第一行：整數(shù)n(2<=n<=200)：村子的個(gè)數(shù)。接下來是一個(gè)n*n的0、1矩陣，表示n個(gè)村子的連同情況，如：a[i,j]=1，表示第i和第j個(gè)村子之間有路可走，如果a[i,j]=0，表示他們之間無路可走。輸出：一條可行的路線輸入：7

0101100

1010100

0100001

1000000

1100010

0000101

0010010輸出：2376514第三十八頁，共八十頁，2022年，8月28日分析題目的限制條件：“途經(jīng)每個(gè)村子僅且經(jīng)過一次”，表明在深搜的過程中，Vi的鄰接點(diǎn)中必須要有至少一個(gè)頂點(diǎn)是沒有被訪問過的。這樣才能沿著該點(diǎn)繼續(xù)DFS下去。如果恰能遍歷全部結(jié)點(diǎn)，則找到一條路徑，輸出這條路徑即可。怎樣在DFS的過程中保存路徑？如果在DFS的某一層出現(xiàn)了所有鄰接點(diǎn)都被訪問過了，則說明在上一層（以及更上層）的路由選擇不正確，這時(shí)就要回溯到上層，換一個(gè)未被訪問的結(jié)點(diǎn),再次進(jìn)行DFS，看能否走通。在換結(jié)點(diǎn)的時(shí)候，一定要清除前一個(gè)結(jié)點(diǎn)被訪問過的標(biāo)志信息，這就是所謂的“清理現(xiàn)場(chǎng)”的工作。如果不做這個(gè)操作，則求解幾乎沒有可能得到正確結(jié)果。第三十九頁，共八十頁，2022年，8月28日constmaxn=100;{算法一}vara:array[1..maxn,1..maxn]ofinteger;visited:array[1..maxn]of0..1;b:array[1..maxn]of1..maxn;n,m,i:integer;found:integer;

procedureinit;vari,j:integer;beginassign(input,'a.in');reset(input);readln(n);fori:=1tondoforj:=1tondoread(a[i,j]);close(input);end;

procedureprint;vari:integer;beginfound:=1;fori:=1ton-1dowrite(b[i],'');writeln(b[n]);end;

proceduredfs(i:integer);varj,k:integer;begin//m是當(dāng)前訪問的結(jié)點(diǎn)個(gè)數(shù)

ifm=nthenbeginprint;exit;end;forj:=1tondoif(a[j,i]=1)and(visited[j]=0)thenbeginvisited[j]:=1;m:=m+1;b[m]:=j;dfs(j);

visited[j]:=0;m:=m-1;end;end;第四十頁，共八十頁，2022年，8月28日

Begininit;found:=0;fori:=1tondobeginfillchar(visited,sizeof(visited),0);m:=1;b[1]:=i;visited[i]:=1;dfs(i);end;iffound=0thenwriteln('noroad');end.第四十一頁，共八十頁，2022年，8月28日{(diào)算法二}proceduredfs(i,k:integer);{結(jié)點(diǎn)i是路上的第k個(gè)結(jié)點(diǎn)}varj:integer;beginifk=nthenprint;forj:=1tondoif(a[j,i]=1)and(visited[j]=0)thenbeginvisited[j]:=1;b[k+1]:=j;dfs(j,k+1);

visited[j]:=0;end;end;Begininit;found:=0;fori:=1tondobeginfillchar(visited,sizeof(visited),0);m:=1;b[1]:=i;visited[i]:=1;dfs(i,1);end;iffound=0thenwriteln('noroad');end.第四十二頁，共八十頁，2022年，8月28日

3、安排座位

n個(gè)客人圍著一個(gè)桌子吃飯，每一個(gè)人都至少認(rèn)識(shí)其他的2個(gè)客人。請(qǐng)?jiān)O(shè)計(jì)程序求得n個(gè)人的一種坐法，使得每個(gè)人都認(rèn)識(shí)他左右的客人。輸入:第一行:n（吃飯人的個(gè)數(shù)）。以下n行：第i行的第一個(gè)數(shù)k表示第i個(gè)人認(rèn)識(shí)的人數(shù)，后面k個(gè)數(shù)依次為i認(rèn)識(shí)的人的編號(hào)。輸出：所有座法，要求第一個(gè)人為1號(hào)作為起點(diǎn)，按順時(shí)針輸出其它人的編號(hào)。樣例輸入：6236345631463235324641235樣例輸出：134256134526162543165243第四十三頁，共八十頁，2022年，8月28日

分析:

如果A認(rèn)識(shí)B,B又認(rèn)識(shí)C,則B認(rèn)識(shí)他左右的兩個(gè)人.繼續(xù)這個(gè)過程,如果C又認(rèn)識(shí)D,則C認(rèn)識(shí)他左右的兩個(gè)人;……這其實(shí)就是一個(gè)DFS過程.如果最后一個(gè)人能認(rèn)識(shí)第一個(gè)人,則最后一個(gè)人也認(rèn)識(shí)他左右的兩個(gè)人.這樣就找到一組滿足要求的解了.本題是求一個(gè)N個(gè)頂點(diǎn)的簡單回路問題.第四十四頁，共八十頁，2022年，8月28日proceduredfs(i:integer);varj,k:integer;beginif(n=m)and(a[b[1],b[m]]=1)thenprint;forj:=1tondoif(a[i,j]=1)and(visited[j]=0)thenbeginvisited[j]:=1;m:=m+1;b[m]:=j;dfs(j);visited[j]:=0;m:=m-1;end;end;Begininit;fillchar(visited,sizeof(visited),0);found:=0;m:=1;b[1]:=1;visited[1]:=1;dfs(1);iffound=0thenwriteln('noroad');end.第四十五頁，共八十頁，2022年，8月28日4、素?cái)?shù)鏈設(shè)計(jì)程序?qū)?,2,…,20排成一排，使任意兩個(gè)相鄰的數(shù)的和為素?cái)?shù)。第1個(gè)和最后一個(gè)的和也為素?cái)?shù).輸出:1~20個(gè)數(shù)的排列方式.第四十六頁，共八十頁，2022年，8月28日constmaxn=100;varvisited:array[1..maxn]of0..1;b:array[1..maxn]of1..maxn;n,m,i:integer;found:integer;

functioncheck(i:integer):boolean;varj:integer;beginforj:=2toi-1doifimodj=0thenbegincheck:=false;exit;end;check:=true;end;

procedureprint;vari:integer;beginfound:=1;fori:=1ton-1dowrite(b[i],'');writeln(b[n]);halt;end;第四十七頁，共八十頁，2022年，8月28日

proceduredfs(i:integer);varj,k:integer;beginif(m=n)and(check(b[1]+b[m]))thenprint;forj:=1tondoif(visited[j]=0)and(check(i+j))thenbeginvisited[j]:=1;m:=m+1;b[m]:=j;dfs(j);visited[j]:=0;m:=m-1;end;end;Beginfillchar(visited,sizeof(visited),0);n:=20;found:=0;m:=1;b[1]:=1;visited[1]:=1;dfs(1);iffound=0thenwriteln('noroad');end.第四十八頁，共八十頁，2022年，8月28日2、廣度（寬度）優(yōu)先搜索BFS廣度優(yōu)先搜索按層次遍歷的過程，其搜索過程如下：方法：從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)后，依次訪問V1的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8第四十九頁，共八十頁，2022年，8月28日V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8第五十頁，共八十頁，2022年，8月28日V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V5第五十一頁，共八十頁，2022年，8月28日在程序中實(shí)現(xiàn)BFS從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)后，依次訪問V1的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；要解決的問題:怎樣依次訪問Vi的鄰接點(diǎn)?怎樣依次從它的鄰接點(diǎn)出發(fā),廣度優(yōu)選遍歷圖?我們用到的主要的數(shù)據(jù)結(jié)構(gòu)就是隊(duì)列.第五十二頁，共八十頁，2022年，8月28日例142350123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143012345fr隊(duì)列空結(jié)點(diǎn)在入隊(duì)時(shí)進(jìn)行訪問，f指針指向當(dāng)前擴(kuò)展結(jié)點(diǎn)11第五十三頁，共八十頁，2022年，8月28日012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：1432511414012345

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：14325143143214325第五十四頁，共八十頁，2022年，8月28日14356782輸入：81014151626273534375758編程實(shí)現(xiàn)：輸入下圖，按深度優(yōu)先遍歷和廣度優(yōu)先遍歷輸出圖的結(jié)點(diǎn)。第五十五頁，共八十頁，2022年，8月28日{(diào)圖的dfs}constmax=100;vara:array[1..max,1..max]ofinteger;f:array[1..max]of0..1;//標(biāo)志數(shù)組

n,m,i:integer;procedureinit;vari,j,x,y:integer;beginreadln(n,m);fillchar(f,sizeof(f),0);fori:=1tomdobeginreadln(x,y);a[x,y]:=1;a[y,x]:=1;end;end;proceduredfs(i:integer);{深搜}varj:integer;beginwrite(i,'');f[i]:=1;forj:=1tondoif(f[j]=0)and(a[i,j]=1)thendfs(j);end;第五十六頁，共八十頁，2022年，8月28日procedurebfs(i:integer);{廣搜}varj,k:integer;beginfillchar(q,sizeof(q),0);f:=0;{隊(duì)首}r:=1;{尾}q[1]:=i;{i進(jìn)隊(duì)列}write(i,'');f[i]:=1;{標(biāo)志}whilef<rdo{隊(duì)列不空}begininc(f);k:=q[f];{出隊(duì)}forj:=1tondoif(a[k,j]=1)and(f[j]=0)thenbeginwrite(j,'');f[j]:=1;inc(r);{進(jìn)隊(duì)}q[r]:=j;end;end;end;BEGINInit;//讀入圖數(shù)據(jù),初始化標(biāo)志數(shù)組Fori:=1tondoiff[i]=0thendfs(i);Writeln;fillchar(f,sizeof(f),0);fori:=1tondoiff[i]=0thenbfs(i);END.第五十七頁，共八十頁，2022年，8月28日[問題描述]

學(xué)校放暑假時(shí)，信息學(xué)輔導(dǎo)教師有n本書要分給參加培訓(xùn)的n個(gè)學(xué)生。如：A，B，C，D，E共5本書要分給參加培訓(xùn)的張、劉、王、李、孫5位學(xué)生，每人只能選1本。教師事先讓每個(gè)人將自己喜愛的書填寫在如下的表中，然后根據(jù)他們填寫的表來分配書本，希望設(shè)計(jì)一個(gè)程序幫助教師求出可能的分配方案，使每個(gè)學(xué)生都滿意。ABCDE張YY王YY劉YY孫Y李YY5、借書問題第五十八頁，共八十頁，2022年，8月28日輸入格式：第一行一個(gè)數(shù)n（學(xué)生的個(gè)數(shù)，書的數(shù)量）以下共n行，每行n個(gè)0或1（由空格隔開），第I行數(shù)據(jù)表示第i個(gè)同學(xué)對(duì)所有書的喜愛情況。0表示不喜歡該書，1表示喜歡該書。輸出格式：依次輸出每個(gè)學(xué)生分到的書號(hào)。樣例：輸入：book.in50011011000011000001001001輸出：book.out31245第五十九頁，共八十頁，2022年，8月28日分析:a:array[1..maxn,1..maxn]of0..1;b:array[1..maxn]ofinteger;{方案:b[i]是第i個(gè)人借第b[i]本書}book:array[1..maxn]ofboolean;{book[[i]:能否可以借第i本書,

初始:true,一旦有人借了:就改為:false}第六十頁，共八十頁，2022年，8月28日算法設(shè)計(jì):proceduretry(i:integer);{搜索第i個(gè)人可以借的書b[i]}varj:integer;beginifi=n+1then輸出結(jié)果

elseforj:=1tondoif第i個(gè)人可以借第j本書thenbegin

記錄下b[i];

標(biāo)記第j本數(shù)已被借;try(i+1);

刪除書的被借標(biāo)志;end;end;第六十一頁，共八十頁，2022年，8月28日constmaxn=10;vara:array[1..maxn,1..maxn]of0..1;b:array[1..maxn]ofinteger;book:array[1..maxn]ofboolean;n:integer;

procedureinit;vari,j:integer;beginassign(input,'book.in');reset(input);fillchar(b,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(a[i,j]);close(input);end;

procedureprint;vari:integer;beginfori:=1ton-1dowrite(b[i],'');writeln(B[N]);end;

proceduretry(i:integer);varj:integer;beginifi=n+1thenprint;forj:=1tondoifbook[j]and(a[i,j]=1)thenbeginb[i]:=j;book[j]:=false;try(i+1);book[j]:=true;end;end;Begininit;try(1);end.第六十二頁，共八十頁，2022年，8月28日火力中心布局(自習(xí))

現(xiàn)有一張由n個(gè)堡壘組成的交通圖，任意兩個(gè)堡壘之間只有一條通行路線。為了確保路線暢通，必須在某些堡壘上建立火力中心，每個(gè)火力中心都能夠?qū)ζ湎噙B的所有交通線進(jìn)行全天候的監(jiān)控，防止敵人侵略?，F(xiàn)在的問題是如何設(shè)置火力中心的布局，才能用最少的火力中心控制所有交通路線。輸入：堡壘數(shù)n(1≤n≤10000)；以下每行為i，j，表示堡壘i與堡壘j連接。以00標(biāo)志結(jié)束；輸出：

w行，每行為火力中心所在的堡壘號(hào)。火力中心數(shù)w第六十三頁，共八十頁，2022年，8月28日數(shù)學(xué)模型和解題的基本思路如果將堡壘設(shè)為頂點(diǎn)、堡壘間的交通線設(shè)為邊的話，則交通圖為一張無向圖。由于任意兩個(gè)堡壘之間只有一條通行路線，且沒有明確出發(fā)點(diǎn)，因此這張無向圖構(gòu)成了一棵無根樹。所謂支配集是圖Ｇ的一個(gè)滿足下述條件的頂點(diǎn)子集：即圖Ｇ的任意頂點(diǎn)或?qū)儆谠摷?，或至少與該集合的一個(gè)頂點(diǎn)相鄰。顯然，火力點(diǎn)就是支配集中的頂點(diǎn)。本題的數(shù)學(xué)模型就是在交通圖對(duì)應(yīng)的無根樹中，計(jì)算含頂點(diǎn)數(shù)最少的最小支配集。如果是一棵明確了頂點(diǎn)間父子關(guān)系的有根樹的話，我們很容易找到計(jì)算最小支配集的方法：按照自底而上、由右而左的順序搜索每一條邊。如果一條邊的兩個(gè)端點(diǎn)為訪問，則父頂點(diǎn)進(jìn)入支配集，由其支配祖父頂點(diǎn)和所有兒子。依次類推，直至根被訪問為止。第六十四頁，共八十頁，2022年，8月28日第一步：建立邊表。由于交通圖為一張無向圖，因此我們將每條邊拆分成方向互為相反的兩條邊，即(xi，yi)作為第i條邊存儲(chǔ)，(yi，xi)作為第n+i條邊存儲(chǔ):fori←1ton-1do{建立邊表。由于是無向圖，因此將第i條邊（k,j）分別存儲(chǔ)于（x[i],y[i]）和（x[n+i-1],y[n+i-1]）}beginreadln(f,x[i],y[i]);{讀第i條邊的兩個(gè)端點(diǎn)}x[i+n-1]←y[i];y[i+n-1]←x[i]{反向存儲(chǔ)第i條邊的兩個(gè)端點(diǎn)}

end;{for}第六十五頁，共八十頁，2022年，8月28日第二步：通過深度優(yōu)先搜索將無根樹轉(zhuǎn)化為明確頂點(diǎn)間父子關(guān)系的有根樹。

首先從頂點(diǎn)1出發(fā)，按照縱深搜索的策略構(gòu)造一棵深度優(yōu)先搜索樹，并記下每個(gè)頂點(diǎn)的父頂點(diǎn)。由于樹邊的父子關(guān)系未明確,因此逐邊搜索。方向是由左而右、由上而下，對(duì)于第i個(gè)被訪問的頂點(diǎn)來說，所有訪問順序比i大的頂點(diǎn)，不是該頂點(diǎn)的后輩頂點(diǎn)就是位于該頂點(diǎn)的右方樹枝上。例如第六十六頁，共八十頁，2022年，8月28日設(shè)cd表為按照深度優(yōu)先搜索順序存儲(chǔ)的被訪問頂點(diǎn)，即第i個(gè)被訪問的頂點(diǎn)為cd[i]。在深度優(yōu)先搜索樹中，其父親為pt[cd[i]]。我們通過遞歸過程encode計(jì)算深度優(yōu)先搜索的訪問順序表cd和父指針表pt：procedureencode(nw,last:integer);{輸入當(dāng)前頂點(diǎn)nw和父頂點(diǎn)last，遞歸計(jì)算cd和pt表}vari:integer;begininc(nm);cd[nm]←nw;{nw進(jìn)入深度優(yōu)先搜索的訪問順序表}cv[nw]←true;pt[nw]←last;{設(shè)nw已訪問，其父頂點(diǎn)為last}fori←1to2*n-2do){遞歸訪問與nw相連的未訪問邊，這些邊的另一端點(diǎn)為nw的兒子}if(x[i]=nw)andnotcv[y[i]]thenencode(y[i],nwend;{encode}第六十七頁，共八十頁，2022年，8月28日第三步：逆推深度優(yōu)先搜索的訪問順序，計(jì)算最小支配集按照深度優(yōu)先搜索的逆向順序，即由右而左、由下而上的順序訪問每個(gè)頂點(diǎn)，依次將每條未訪問邊（父子頂點(diǎn)未訪問）的父頂點(diǎn)設(shè)為火力點(diǎn),由其控制祖父頂點(diǎn)和所有兒子。例如圖，可在第1、3、5個(gè)被訪問的頂點(diǎn)處布局火力點(diǎn)。第六十八頁，共八十頁，2022年，8月28日主程序建立邊表x和y；fillchar(cv,sizeof(cv),0);nm←0;{訪問表cv和訪問順序表cd的長度初始化}encode(1,1);{從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索，計(jì)算訪問順序表cd和父指針表pt}fillchar(cv,sizeof(cv),0);w←0;{訪問表cv和火力點(diǎn)數(shù)初始化}fori←ndownto2do{按照由右而左、由下而上的順序訪問每個(gè)頂點(diǎn)，依次將每條未訪問邊（父子頂點(diǎn)未訪問）的父頂點(diǎn)設(shè)為火力點(diǎn)}ifnotcv[cd[i]]andnotcv[pt[cd[i]]]{若深度優(yōu)先搜索中第i個(gè)被訪問的頂點(diǎn)和其父親當(dāng)前未訪問，則其父親設(shè)為火力點(diǎn)}thenbegininc(w);write(pt[cd[i]],'');{在父端點(diǎn)處增設(shè)一個(gè)火力點(diǎn)，輸出該火力點(diǎn)序號(hào)}cv[pt[cd[i]]]←true{置火力點(diǎn)已訪問標(biāo)志}end;{then}writeln(w);{輸出火力點(diǎn)數(shù)}第六十九頁，共八十頁，2022年，8月28日第七十頁，共八十頁，2022年，8月28日任務(wù)A:

題目給出一個(gè)完整路線（圖），請(qǐng)編程找出所有必經(jīng)之點(diǎn)。請(qǐng)注意，輸出必經(jīng)之點(diǎn)時(shí)，應(yīng)不包括起點(diǎn)和終點(diǎn)。任務(wù)B:

假定賽跑必須在相鄰的2天來舉行。因此，要把原來給定的完整路線（圖）分成兩個(gè)子路線（圖）。第1天從點(diǎn)0出發(fā)，結(jié)束于“分裂點(diǎn)”。第2天從“分裂點(diǎn)”出發(fā)，結(jié)束于點(diǎn)N。題目給出一個(gè)完整路線（圖）C，請(qǐng)編程輸出所有可能的“分裂點(diǎn)”（任務(wù)B）?！胺至腰c(diǎn)”S一定不是起點(diǎn)或終點(diǎn)。C可被S分成兩個(gè)完整的子路線：這兩個(gè)子路線沒有公共的箭頭線，并且S是這兩個(gè)子路線的唯一公共點(diǎn)。在上的例子中，僅點(diǎn)3是“分裂點(diǎn)”。輸入數(shù)據(jù)輸入文件INPUT．TXT描述一個(gè)完整路線（最多50個(gè)點(diǎn)，最多100個(gè)箭頭），文件共（n＋1）行。前面n行（0－（n-1））描述箭頭的終點(diǎn)。第i行中的每一個(gè)數(shù)字表示從點(diǎn)i（0≤i≤n－1）出發(fā)的每一個(gè)箭頭的終點(diǎn)。以－2作為該行的結(jié)束。文件的最后一行（第n行）中有一個(gè)數(shù)字－1，表示文件的結(jié)束。輸出