上傳人：姚***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：姚**（實(shí)名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2023-04-20 格式：PPT 頁(yè)數(shù)：53 大小：2.90MB 積分：28 舉報(bào) 版權(quán)申訴

圖的基本概念及拓?fù)渑判虻?頁(yè)，共53頁(yè)，2023年，2月20日，星期六什么是圖？什么是圖?可用一句話概括，即：圖是用點(diǎn)和線來(lái)刻劃離散事物集合中的每對(duì)事物間以某種方式相聯(lián)系的數(shù)學(xué)模型.因?yàn)樗@得太抽象，不便于理解，所以有必要給出另外的回答.第2頁(yè)，共53頁(yè)，2023年，2月20日，星期六1圖的基本術(shù)語(yǔ)圖：記為G＝(V,E)

其中：V

是G的頂點(diǎn)集合，是有窮非空集；E

是G的邊集合，是有窮集。有向圖：無(wú)向圖：圖G中的每條邊都是有方向的；圖G中的每條邊都是無(wú)方向的；若

n個(gè)頂點(diǎn)的無(wú)向圖有

n(n-1)/2條邊,

稱為無(wú)向完全圖若

n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖V=vertexE=edge第3頁(yè)，共53頁(yè)，2023年，2月20日，星期六例：判斷下列4種圖形各屬什么類型？無(wú)向無(wú)向圖(樹(shù))有向圖有向完全圖完全圖第4頁(yè)，共53頁(yè)，2023年，2月20日，星期六稀疏圖：

稠密圖：設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,則稱圖G’是圖G的子圖。子圖：邊較少的圖。通常邊數(shù)<<n2邊很多的圖。無(wú)向圖中，邊數(shù)接近n(n-1)/2；

有向圖中，邊數(shù)接近n(n-1)補(bǔ)圖：

定義1：設(shè)圖G1=<V1，E1>和圖G2=<V2，E2>是圖G=<V，E>的子圖.如果E2=E-E1且G2=<E2>，則稱圖G2是相對(duì)于圖G的子圖G1的補(bǔ)圖.定義2：給定圖G=<V，E>，若存在圖G1=<V，E1>，并且E1∩E=和圖<V，E1∪E>是完全圖，則G1稱為相對(duì)于完全圖的G的補(bǔ)圖，簡(jiǎn)稱G1是G的補(bǔ)圖.

第5頁(yè)，共53頁(yè)，2023年，2月20日，星期六帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。＝帶權(quán)圖網(wǎng)絡(luò)：

路徑：在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vivp1vp2...vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)當(dāng)是屬于E的邊。非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。

路徑長(zhǎng)度：第6頁(yè)，共53頁(yè)，2023年，2月20日，星期六連通圖：在無(wú)向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖：在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。

非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。第7頁(yè)，共53頁(yè)，2023年，2月20日，星期六生成樹(shù)：鄰接點(diǎn)：

頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。

頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v);

頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。若(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn)度、入度和出度：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。如果在生成樹(shù)上添加1條邊，必定構(gòu)成一個(gè)環(huán)。若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。最小生成樹(shù)：若無(wú)向連通帶權(quán)圖G=<V,E,W>,T是G的一棵生成樹(shù)，T的各邊權(quán)之和稱為T(mén)的權(quán)，記做W（T），G的所有生成樹(shù)中權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)。最小生成樹(shù)算法：Prim算法和kruskal算法第8頁(yè)，共53頁(yè)，2023年，2月20日，星期六簡(jiǎn)單路徑：路徑上各頂點(diǎn)v1,v2,...,vm

均不互相重復(fù)?；芈罚豪喝袈窂缴系谝粋€(gè)頂點(diǎn)v1

與最后一個(gè)頂點(diǎn)vm

重合，則稱這樣的路徑為回路或環(huán)。第9頁(yè)，共53頁(yè)，2023年，2月20日，星期六圖的數(shù)學(xué)表示

點(diǎn):用整數(shù)0,1,2,…,V-1表示

邊:用無(wú)序數(shù)對(duì)(u,v)表示,或者表示成u-v第10頁(yè)，共53頁(yè)，2023年，2月20日，星期六7.2圖的存儲(chǔ)結(jié)構(gòu)重點(diǎn)介紹：鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法主要有下面四種方法：鄰接矩陣鄰接表十字鏈表多重鏈表第11頁(yè)，共53頁(yè)，2023年，2月20日，星期六一、鄰接矩陣（數(shù)組）表示法建立一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。設(shè)圖A=(V,E)有n

個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.Edge[n][n]，定義為：1235v44A例1：鄰接矩陣：A.Edge=（

12

345

）1234500

0

0000

0000

0000000000000001

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10頂點(diǎn)表：第12頁(yè)，共53頁(yè)，2023年，2月20日，星期六例2：有向圖的鄰接矩陣v1v2v3v4A鄰接矩陣：A.Edge=(

v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為起點(diǎn)的邊(即出邊）；第i列含義：以結(jié)點(diǎn)vi為終點(diǎn)的弧(即入邊）。頂點(diǎn)表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

000第13頁(yè)，共53頁(yè)，2023年，2月20日，星期六特別討論：網(wǎng)（即有權(quán)圖）的鄰接矩陣定義為：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞

無(wú)邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣：N.Edge=(12

3456)頂點(diǎn)表：∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞第14頁(yè)，共53頁(yè)，2023年，2月20日，星期六圖的鄰接矩陣表示示例intadjlist[max_vex_num][max_vex_num];

說(shuō)明：adjlist[i][j]若無(wú)權(quán)圖無(wú)重邊則直接用01表示Ij兩點(diǎn)是否直接鄰接若無(wú)權(quán)圖有重邊則直接用01….表示是Ij兩點(diǎn)之間邊的個(gè)數(shù)若有權(quán)圖則用來(lái)表示Ij兩點(diǎn)之間的距離或者其他權(quán)值

第15頁(yè)，共53頁(yè)，2023年，2月20日，星期六二、鄰接表（鏈?zhǔn)剑┍硎痉▽?duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊（即度或出度邊）鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為2個(gè)域；adjvexnextarc權(quán)值datafirstarc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi

的序號(hào)鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)第16頁(yè)，共53頁(yè)，2023年，2月20日，星期六鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；一般用于稀疏圖判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。鄰接表鄰接矩陣存儲(chǔ)比較鄰接矩陣的優(yōu)點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，可以直接判斷速度很快一般用于存儲(chǔ)稠密圖鄰接矩陣的缺點(diǎn)：存儲(chǔ)空間大會(huì)影響算法的空間效率甚至?xí)r間效率第17頁(yè)，共53頁(yè)，2023年，2月20日，星期六討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)第18頁(yè)，共53頁(yè)，2023年，2月20日，星期六圖的搜索方法1廣度優(yōu)先搜索2深度優(yōu)先搜索第19頁(yè)，共53頁(yè)，2023年，2月20日，星期六一、廣度優(yōu)先遍歷(BFS)

有時(shí)也叫寬度優(yōu)先遍歷第20頁(yè)，共53頁(yè)，2023年，2月20日，星期六基本算法由Moore和Lee獨(dú)立提出給定圖G和一個(gè)源點(diǎn)s,寬度優(yōu)先遍歷按照從近到遠(yuǎn)的順序考慮各條邊.算法求出從s到各點(diǎn)的距離寬度優(yōu)先的過(guò)程對(duì)結(jié)點(diǎn)著色.白色:沒(méi)有考慮過(guò)的點(diǎn)黑色:已經(jīng)完全考慮過(guò)的點(diǎn)灰色:發(fā)現(xiàn)過(guò),但沒(méi)有處理過(guò),是遍歷邊界依次處理每個(gè)灰色結(jié)點(diǎn)u,對(duì)于鄰接邊(u,v),把v著成灰色并加入樹(shù)中,在樹(shù)中u是v的父親(parent)或稱前驅(qū)(predecessor).距離d[v]=d[u]+1整棵樹(shù)的根為s第21頁(yè)，共53頁(yè)，2023年，2月20日，星期六BFS算法BFS(G,s)//從s點(diǎn)開(kāi)始對(duì)圖G廣度優(yōu)先搜索foreachvertexu∈V[G]-{s}docolor[u]←white//每個(gè)點(diǎn)賦值為未處理d[u]←∞//每個(gè)點(diǎn)與源點(diǎn)的距離標(biāo)志為∞∏[u]←NIL//每個(gè)點(diǎn)賦值為沒(méi)有父親color[s]←gray//s點(diǎn)標(biāo)為正在處理d[s]←0//s點(diǎn)與源點(diǎn)的距離為0Q←ф//建空隊(duì)列保存灰色頂點(diǎn)ENQUEUE(Q,s)//源點(diǎn)入隊(duì)列While（Q≠ф）dou←DEQUEUE(Q);//從隊(duì)列中拿出一個(gè)元素進(jìn)行處理foreachv∈Adj[u]//對(duì)沒(méi)有處理過(guò)的鄰接點(diǎn)進(jìn)行處理doifcolor[v]=whitethencolor[v]←grayd[v]=d[u]+1∏[v]=uENQUEUE(Q,v)color[u]=black//標(biāo)記為處理完畢第22頁(yè)，共53頁(yè)，2023年，2月20日，星期六第23頁(yè)，共53頁(yè)，2023年，2月20日，星期六用BFS求最短路定理:對(duì)于無(wú)權(quán)圖(每條邊的長(zhǎng)度為1),BFS算法計(jì)算出的d[i]是從s到i的最短路滿足d[i]=1的點(diǎn)一定是正確的(因?yàn)殚L(zhǎng)度至少為1),并且其他點(diǎn)都滿足d[i]>1.容易證明對(duì)于任意距離值x,d[i]=x的點(diǎn)一定是正確的,而且白色點(diǎn)(沒(méi)有計(jì)算出距離的點(diǎn))的距離一定至少為x+1更進(jìn)一步,根據(jù)每個(gè)點(diǎn)的parent值,可以計(jì)算出它到s的一條最短路第24頁(yè)，共53頁(yè)，2023年，2月20日，星期六Bfs算法中路徑的打印Print-Path(G,s,v)if(v==s)thenprintselseif∏[v]=NILthenprint“nopathfrom”s”to”v”exits”elsePrint-path(G,s,∏[v])printv第25頁(yè)，共53頁(yè)，2023年，2月20日，星期六機(jī)器人問(wèn)題Dr.Kong是設(shè)計(jì)了一個(gè)可以前進(jìn)或者后退的機(jī)器人，該機(jī)器人在每一個(gè)位置i會(huì)得到一個(gè)移動(dòng)的步數(shù)指令Ki（i=1，2···n），聰明的機(jī)器人會(huì)自己判斷是要前進(jìn)Ki步還是要后退Ki步。例如：給定指令序列（3，3，1，2，5），表示機(jī)器人在第一個(gè)位置時(shí)，可以前進(jìn)3步到第4個(gè)位置，此時(shí)后退是不起作用的，出界：機(jī)器人在第2個(gè)位置時(shí)，可以前進(jìn)3步到第5個(gè)位置，此時(shí)后退時(shí)不起作用的，出界：機(jī)器人在第3個(gè)位置的時(shí)，可以前進(jìn)1步到第4個(gè)位置，也可以后退一步到第2個(gè)位置等等.你認(rèn)為，對(duì)于給定的兩個(gè)位置A，B，聰明的機(jī)器人從A位置到B位置至少需要判斷幾次？input第一行：M表示以下有M組測(cè)試數(shù)據(jù)（0<M<=8）接下來(lái)每組有兩行數(shù)據(jù)頭一行：NAB（1<=N<=50,1<=A,B<=N）下一行：K1K2···Kn（0<=Ki<=N）output輸出有M行，第i行為第i組測(cè)試數(shù)據(jù)的最少判斷次數(shù)，若無(wú)法到達(dá)，則輸出-1。樣例輸入25153312585312153111樣例輸出3-1第26頁(yè)，共53頁(yè)，2023年，2月20日，星期六分析發(fā)現(xiàn)這道題目就是用寬度優(yōu)先搜索求最短路徑的題目有n個(gè)頂點(diǎn)Ki表示i------i+Ki和i-----i-ki之間有通路（當(dāng)然i+Ki，i-ki為合法頂點(diǎn)）求A----B的最少判斷次數(shù)就是求A——B的最短路徑通廣搜可以求出最短路徑第27頁(yè)，共53頁(yè)，2023年，2月20日，星期六機(jī)器人問(wèn)題boolargs[51][51];intd[51];boolvisited[51];memset(args,false,sizeof(args));memset(d,0xfffff,sizeof(d));memset(visited,false,sizeof(visited));intn,a,b;cin>>n>>a>>b;for(inti=1;i<=n;i++){ inttemp; cin>>temp; if(i+temp<=n)args[i][i+temp]=true; if(i-temp>=1)args[i][i-temp]=true;}

d[a]=0;visited[a]=true;queue<int>q;q.push(a);while(!q.empty()){inttemp=q.front(); q.pop(); for(inti=0;i<=n;i++) { if(args[temp][i]&&!visited[i]) { d[i]=d[temp]+1; visited[i]=true; q.push(i); }}}cout<<d[b]<<endl;第28頁(yè)，共53頁(yè)，2023年，2月20日，星期六二、深度優(yōu)先遍歷(DFS)第29頁(yè)，共53頁(yè)，2023年，2月20日，星期六深度優(yōu)先搜索(DFS)基本思想：——仿樹(shù)的先序遍歷過(guò)程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS結(jié)果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS結(jié)果v4→v6起點(diǎn)起點(diǎn)遍歷步驟第30頁(yè)，共53頁(yè)，2023年，2月20日，星期六深度優(yōu)先搜索（遍歷）步驟：詳細(xì)歸納：在訪問(wèn)圖中某一起始頂點(diǎn)

v

后，由

v出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)

w1；再?gòu)?/p>

w1出發(fā)，訪問(wèn)與

w1鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn)

w2；然后再?gòu)?/p>

w2出發(fā)，進(jìn)行類似的訪問(wèn)，…

如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)

u為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。

如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；

如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。簡(jiǎn)單歸納：訪問(wèn)起始點(diǎn)v;

若v的第1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。第31頁(yè)，共53頁(yè)，2023年，2月20日，星期六基本算法新發(fā)現(xiàn)的結(jié)點(diǎn)先擴(kuò)展得到的可能不是一棵樹(shù)而是森林,即深度優(yōu)先森林(Depth-firstforest)特別之處:引入時(shí)間戳(timestamp)發(fā)現(xiàn)時(shí)間d[v]:變灰的時(shí)間結(jié)束時(shí)間f[v]:變黑的時(shí)間1<=d[v]<f[v]<=2|V|初始化:time為0,所有點(diǎn)為白色,dfs森林為空對(duì)每個(gè)白色點(diǎn)u執(zhí)行一次DFS-VISIT(u)第32頁(yè)，共53頁(yè)，2023年，2月20日，星期六DFS-VISIT算法初始化:time為0,所有點(diǎn)為白色,dfs森林為空對(duì)每個(gè)白色點(diǎn)u執(zhí)行一次DFS-VISIT(u)時(shí)間復(fù)雜度為O(n+m)第33頁(yè)，共53頁(yè)，2023年，2月20日，星期六第34頁(yè)，共53頁(yè)，2023年，2月20日，星期六DFS樹(shù)的性質(zhì)括號(hào)結(jié)構(gòu)性質(zhì)對(duì)于任意結(jié)點(diǎn)對(duì)(u,v),考慮區(qū)間[d[u],f[u]]和[d[v],f[v]],以下三個(gè)性質(zhì)恰有一個(gè)成立:完全分離u的區(qū)間完全包含在v的區(qū)間內(nèi),則在dfs樹(shù)上u是v的后代v的區(qū)間完全包含在u的區(qū)間內(nèi),則在dfs樹(shù)上v是u的后代三個(gè)條件非常直觀第35頁(yè)，共53頁(yè)，2023年，2月20日，星期六DFS樹(shù)的性質(zhì)定理1(嵌套區(qū)間定理):在DFS森林中v是u的后代當(dāng)且僅當(dāng)d[u]<d[v]<f[v]<f[u],即區(qū)間包含關(guān)系.由區(qū)間性質(zhì)立即得到.定理2(白色路徑定理):在DFS森林中v是u的后代當(dāng)且僅當(dāng)在d[u]時(shí)刻(u剛剛被發(fā)現(xiàn)),v可以由u出發(fā)只經(jīng)過(guò)白色結(jié)點(diǎn)到達(dá).證明:由嵌套區(qū)間定理可以證明第36頁(yè)，共53頁(yè)，2023年，2月20日，星期六非遞歸形式的深度優(yōu)先搜索算法voidDFS(GraphG,intv){//非遞歸算法InitStack(S);visited[]=FALSE;//所有的頂點(diǎn)尚未被訪問(wèn)過(guò)Push(S,v);//其實(shí)頂點(diǎn)壓棧while(!Empty(S)){Pop(S,u);//訪問(wèn)頂點(diǎn)并修改標(biāo)志數(shù)組if(!visited[u]){visit(u),visited[u]=TRUE};for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){if(!visited[w])Push(G,w)}//將沒(méi)訪問(wèn)的鄰接點(diǎn)壓棧}DestroyStack(S);//釋放棧}//DFS第37頁(yè)，共53頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)書(shū)上的深度優(yōu)先搜索算法boolvisited[max];//訪問(wèn)標(biāo)志數(shù)組Status(*VisitFunc)(intv);//函數(shù)變量voidDESTraverse(GraphG,status(*visit)(intv)){//對(duì)圖G進(jìn)行深度優(yōu)先搜索（圖G連通與否都可以）visitFunc=visit;//使用全局變量Visitfunc，使DFS函數(shù)不必設(shè)置函數(shù)指針//訪問(wèn)標(biāo)志數(shù)組初始化為全部沒(méi)有訪問(wèn)for(v=0,v<G.vecnum;++v)visitd[v]=false;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//對(duì)尚未訪問(wèn)的結(jié)點(diǎn)進(jìn)行DFS訪問(wèn)}VoidDFS(GraphG,intv){//從第v個(gè)頂點(diǎn)開(kāi)始遞歸的深度優(yōu)先搜索圖Gvisited[v]=true;visit(v);//訪問(wèn)第v個(gè)頂點(diǎn)并修改標(biāo)志位for(w=firstAdivex(G,v),w>=0;w=nextAdjvex(G,v,w))if(!visited[w])DFS(G,w);//對(duì)v的尚未訪問(wèn)過(guò)的鄰接點(diǎn)w遞歸調(diào)用DFS}如果是連通圖此處的DFS只會(huì)被執(zhí)行一次如果是非連通圖此處DFS執(zhí)行的次數(shù)就是連通分支數(shù)第38頁(yè)，共53頁(yè)，2023年，2月20日，星期六圖的連通性問(wèn)題對(duì)于無(wú)向圖若是連通圖則從圖中任意頂點(diǎn)出發(fā)進(jìn)行廣搜或者深搜便可以訪問(wèn)到圖中的任意頂點(diǎn)非連通圖則需要多次調(diào)用DFS才可全部訪問(wèn)每次DFS可以訪問(wèn)一個(gè)連通分量中的所有頂點(diǎn)調(diào)用DFS的次數(shù)為圖的連通分支數(shù)另外采用并查集也可以解決這個(gè)問(wèn)題，并且空間效率比較低。最后若能歸并成一個(gè)幾何則說(shuō)明為連通的，若最后是多個(gè)集合則說(shuō)明是非連通圖對(duì)于有向圖：以后在學(xué)習(xí)的過(guò)程中會(huì)做深入的探討第39頁(yè)，共53頁(yè)，2023年，2月20日，星期六

深搜示例：/JudgeOnline/problem?id=2386

題目大意：如左圖所示一塊矩形地其中‘W’代表的是水‘.’代表的是陸地其中我們認(rèn)為每個(gè)方格和它的八個(gè)方向全部是鄰接的問(wèn)其中有多少池塘題目分析訪問(wèn)一次水方格，我們可以將其8個(gè)方向的水方格全部訪問(wèn)，這樣我們對(duì)一個(gè)水方格進(jìn)行深搜就可以將與其之間有路徑的所有點(diǎn)全部訪問(wèn)。既是可以訪問(wèn)一個(gè)連通分支（也就是一個(gè)湖）。搜索的次數(shù)就是湖的個(gè)數(shù)第40頁(yè)，共53頁(yè)，2023年，2月20日，星期六示例代碼：#include<iostream>usingnamespacestd;inta[101][101];//記錄矩形方格對(duì)應(yīng)的是水還是陸地intsum,n,m;//sum記錄湖的個(gè)數(shù)n矩形地的行數(shù)m矩形地的列數(shù)intflag[101][101];//標(biāo)記每個(gè)方格是否已經(jīng)被訪問(wèn)過(guò)//定義的個(gè)方向intd[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};//檢查xy是否出界boolcheck(intx,inty){ if(x>0&&x<=n&&y>0&&y<=m) return1; return0;}//以一個(gè)方格開(kāi)始深度優(yōu)先搜索voiddfs(intx,inty){ if(flag[x][y]||!a[x][y])//點(diǎn)已經(jīng)訪問(wèn)或者是陸地則停止訪問(wèn) return; flag[x][y]=1;//標(biāo)記當(dāng)前結(jié)點(diǎn)已經(jīng)訪問(wèn) for(inti=0;i<8;i++)//對(duì)當(dāng)前方格的個(gè)鄰接方格進(jìn)行深搜 if(check(x+d[i][0],y+d[i][1])) dfs(x+d[i][0],y+d[i][1]);}第41頁(yè)，共53頁(yè)，2023年，2月20日，星期六intmain(){ inti,j; charc; while(cin>>n>>m) { memset(flag,0,sizeof(flag));//全部方格標(biāo)記為沒(méi)有訪問(wèn) memset(a,0,sizeof(a));//方格全部標(biāo)記為陸地 sum=0;//初始化湖的個(gè)數(shù)為 for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>c; if(c=='W')a[i][j]=1;//是水的方格標(biāo)記為水 } for(i=1;i<=n;i++) for(j=1;j<=m;j++)//對(duì)是水且未被訪問(wèn)過(guò)的方格進(jìn)行深搜 if(a[i][j]&&!flag[i][j])//每次訪問(wèn)訪問(wèn)一個(gè)連通分支即一個(gè)湖 dfs(i,j),sum++; cout<<sum<<endl; } return0;}對(duì)于無(wú)向圖的連通分支數(shù)的判斷既可以用廣度優(yōu)先搜索也可以用深度優(yōu)先搜索大家一定要試著寫(xiě)一下此題的廣度優(yōu)先搜索代碼第42頁(yè)，共53頁(yè)，2023年，2月20日，星期六推薦題目搜索經(jīng)典題目迷宮求解：用一個(gè)矩形表示地圖，其中矩形由方格組成，每個(gè)方格為路或者是墻。給你一個(gè)起點(diǎn)位置和一個(gè)終止位置，問(wèn)你是否能從開(kāi)頭位置到達(dá)終點(diǎn)位置，我們認(rèn)為起始位置和終點(diǎn)位置是不重合的，并且我們只能走直路，不可以走斜路。我們保證起點(diǎn)和終點(diǎn)都是空位置。要求你求一下這條路徑是否存在，存在的話。求出路徑的長(zhǎng)度輸入說(shuō)明：第一行mn代表矩形是m行n列的pqrs，（p，q）開(kāi)始位置，（r，s）目標(biāo)位置接下來(lái)的m行每行共n個(gè)01代碼，其中0代表是通路，1代表是墻。輸出說(shuō)明：有路徑輸出yes并輸出最短路徑各一行，沒(méi)有路徑直接輸出no占一行示例輸入：2200110100示例輸出：yes2思路深搜只能求是否有通路，廣搜是否有通路和最短路徑都可以求出來(lái)/showproblem.php?pid=1253/showproblem.php?pid=1372/showproblem.php?pid=1198/showproblem.php?pid=1232老隊(duì)員可以自己在網(wǎng)上搜一些題目做第43頁(yè)，共53頁(yè)，2023年，2月20日，星期六拓?fù)渑判騿?wèn)題第44頁(yè)，共53頁(yè)，2023年，2月20日，星期六C1

高等數(shù)學(xué)

C2

程序設(shè)計(jì)基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級(jí)語(yǔ)言程序設(shè)計(jì)C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計(jì)算機(jī)原理C8

課程代號(hào)課程名稱先修課程第45頁(yè)，共53頁(yè)，2023年，2月20日，星期六學(xué)生課程學(xué)習(xí)工程圖第46頁(yè)，共53頁(yè)，2023年，2月20日，星期六檢測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉Ｈ绻ㄟ^(guò)拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?，則該AOV網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說(shuō)明AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。第47頁(yè)，共53頁(yè)，2023年，2月20日，星期六例如，對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨镃1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9