數(shù)據(jù)結(jié)構(gòu)第次課圖1第一頁(yè)，共四十一頁(yè)，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容多對(duì)多（m:n)2第二頁(yè)，共四十一頁(yè)，2022年，8月28日7.1基本術(shù)語(yǔ)7.2存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的其他運(yùn)算7.5圖的應(yīng)用第7章圖3第三頁(yè)，共四十一頁(yè)，2022年，8月28日7.1圖的基本術(shù)語(yǔ)圖：記為G＝(V,E)

其中：V

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

E

是G的邊集合，是有窮集。問(wèn)：當(dāng)E(G)為空時(shí)，圖G存在否？答：還存在！但此時(shí)圖G只有頂點(diǎn)而沒有邊。有向圖：無(wú)向圖：完全圖：圖G中的每條邊都是有方向的；圖G中的每條邊都是無(wú)方向的；圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；若

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

n(n-1)/2條邊,

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

n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖V=vertexE=edge4第四頁(yè)，共四十一頁(yè)，2022年，8月28日例：判斷下列4種圖形各屬什么類型？無(wú)向無(wú)向圖(樹)有向圖有向n(n-1)/2條邊n(n-1)條邊G1的頂點(diǎn)集合為V(G1)={0,1,2,3}邊集合為E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全圖完全圖5第五頁(yè)，共四十一頁(yè)，2022年，8月28日

稀疏圖：邊較少的圖。通常邊數(shù)<<n2

子圖：設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且

E’E,則稱圖G’是圖G的子圖。稠密圖：邊很多的圖。無(wú)向圖中，邊數(shù)接近n(n-1)/2

；

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

帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。網(wǎng)絡(luò)：＝帶權(quán)圖6第六頁(yè)，共四十一頁(yè)，2022年，8月28日簡(jiǎn)單路徑：路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù)?；芈罚豪喝袈窂缴系谝粋€(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。路徑：在圖G＝(V,E)中,若從頂點(diǎn)

vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)

vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列

(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)

vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)當(dāng)是屬于E的邊。路徑長(zhǎng)度：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。7第七頁(yè)，共四十一頁(yè)，2022年，8月28日例157324G26例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5(路徑上結(jié)點(diǎn)數(shù)-1)簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，18第八頁(yè)，共四十一頁(yè)，2022年，8月28日弧頭和弧尾：有向邊(u,v)稱為弧，邊的始點(diǎn)u叫弧尾，終點(diǎn)v叫弧頭頂點(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)。鄰接頂點(diǎn)：若(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn)度、入度和出度：?jiǎn)枺寒?dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？答：是樹！而且是一棵有向樹！9第九頁(yè)，共四十一頁(yè)，2022年，8月28日生成樹：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。如果在生成樹上添加1條邊，必定構(gòu)成一個(gè)環(huán)。若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。生成森林：由若干棵生成樹組成，含全部頂點(diǎn)，但構(gòu)成這些樹的邊是最少的。V1V2V4V5V3V7V6V8例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V810第十頁(yè)，共四十一頁(yè)，2022年，8月28日連通圖：在無(wú)向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。強(qiáng)連通圖：有兩類圖形不在本章討論之列：連通圖245136強(qiáng)連通圖356536非連通圖連通分量11第十一頁(yè)，共四十一頁(yè)，2022年，8月28日ADTGraph

{數(shù)據(jù)對(duì)象V：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}；VR={<v,w>|v,w∈V且P(v,w),

<v,w>表示從v到w的弧，

謂詞P(v,w)定義了弧<v,w>的意義或信息}基本操作P：

CreatGraph

(G,V,VR);

初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。

操作結(jié)果：按V和VR的定義構(gòu)造圖G。InsertVex(G,v);

初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。

操作結(jié)果：在圖G中添加新頂點(diǎn)。

………………（參見P135-136）}圖的抽象數(shù)據(jù)類型注意：V的大小寫含義不同！12第十二頁(yè)，共四十一頁(yè)，2022年，8月28日7.2圖的存儲(chǔ)結(jié)構(gòu)圖的特點(diǎn)：非線性結(jié)構(gòu)（m:n）鄰接表鄰接多重表十字鏈表設(shè)計(jì)為鄰接矩陣鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：無(wú)！（多個(gè)頂點(diǎn)，無(wú)序可言）但可用數(shù)組描述元素間關(guān)系?？捎枚嘀劓湵碇攸c(diǎn)介紹：鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法13第十三頁(yè)，共四十一頁(yè)，2022年，8月28日一、鄰接矩陣（數(shù)組）表示法建立一個(gè)頂點(diǎn)表（記錄各個(gè)頂點(diǎn)信息）和一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。設(shè)圖A=(V,E)有n個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.Edge[n][n]，定義為：v1v2v3v5v4v4A例1：鄰接矩陣：A.Edge=（v1v2

v3v4v5

）v1v2v3v4v500

0

0000

0000

00000000000000分析1：無(wú)向圖的鄰接矩陣是對(duì)稱的，對(duì)角元素為0

；分析2：頂點(diǎn)i的度＝第i行(列)中1

的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10頂點(diǎn)表：14第十四頁(yè)，共四十一頁(yè)，2022年，8月28日例2：有向圖的鄰接矩陣分析1：有向圖的鄰接矩陣可能是不對(duì)稱的。分析2：頂點(diǎn)的出度=第i行元素之和，OD(Vi)=A.Edge[i][j]

頂點(diǎn)的入度=第i列元素之和。ID(Vi)=A.Edge[j][i]

頂點(diǎn)的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4A鄰接矩陣：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

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

1

000

000

0

01

1

00001

1

000

000

0

01

1

00015第十五頁(yè)，共四十一頁(yè)，2022年，8月28日容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。特別討論：網(wǎng)（即有權(quán)圖）的鄰接矩陣定義為：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞無(wú)邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(

v1v2

v3v4v5v6)鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：頂點(diǎn)表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞16第十六頁(yè)，共四十一頁(yè)，2022年，8月28日關(guān)聯(lián)矩陣——表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)，e0條邊的圖，G的關(guān)聯(lián)矩陣A是具有以下性質(zhì)的ne階矩陣?yán)?5324G2123456432156A[i][j]=1

i頂點(diǎn)與j

邊相連0i頂點(diǎn)與j

邊不相連對(duì)無(wú)向圖：17第十七頁(yè)，共四十一頁(yè)，2022年，8月28日A[i][j]=1

i頂點(diǎn)與j

邊相連,且i為尾0i頂點(diǎn)與j

邊不相連-1i頂點(diǎn)與j

邊相連,且i為頭對(duì)有向圖：例BDAC123456ABCD43215618第十八頁(yè)，共四十一頁(yè)，2022年，8月28日4321例G124131234特點(diǎn)關(guān)聯(lián)矩陣每列只有兩個(gè)非零元素，是稀疏矩陣；n越大，零元素比率越大無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是關(guān)聯(lián)矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行中“1”的個(gè)數(shù)頂點(diǎn)Vi的入度是A中第i行中“-1”的個(gè)數(shù)19第十九頁(yè)，共四十一頁(yè)，2022年，8月28日二、鄰接表（鏈?zhǔn)剑┍硎痉▽?duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域；每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；adjvexnextarcinfodatafirstarc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。20第二十頁(yè)，共四十一頁(yè)，2022年，8月28日例1：無(wú)向圖的鄰接表v1v2v3v5v4v4鄰接表01234^1334^142^0例2：有向圖的鄰接表v1v2v3v4V4V3^V2V12^3^0^1鄰接表(出邊)V4V3V2V1^3^0^2^0逆鄰接表(入邊)注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。v1v2v3v4v523^142^021第二十一頁(yè)，共四十一頁(yè)，2022年，8月28日例3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！22第二十二頁(yè)，共四十一頁(yè)，2022年，8月28日分析1:

對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(e<<n2)，則比鄰接矩陣表示法O(n2)省空間。鄰接表存儲(chǔ)法的特點(diǎn)：分析2:

在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適?！鋵?shí)是對(duì)鄰接矩陣法的一種改進(jìn)怎樣計(jì)算無(wú)向圖頂點(diǎn)的度？鄰接表的缺點(diǎn)：怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)Vi的度：需遍歷全表鄰接表的優(yōu)點(diǎn)：TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)OD(Vi)＝單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)ID(Vi)＝鄰接點(diǎn)為Vi的弧個(gè)數(shù)TD(Vi)=OD(Vi)+ID(Vi)空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣方便。23第二十三頁(yè)，共四十一頁(yè)，2022年，8月28日討論：鄰接表與鄰接矩陣有什么異同之處？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)24第二十四頁(yè)，共四十一頁(yè)，2022年，8月28日三、十字鏈表（自學(xué)）

（適用于有向圖）

四、鄰接多重表（自學(xué)）

（適用于無(wú)向圖）25第二十五頁(yè)，共四十一頁(yè)，2022年，8月28日

它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。

思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。1、每條弧對(duì)應(yīng)一個(gè)結(jié)點(diǎn)(稱為弧結(jié)點(diǎn)，設(shè)5個(gè)域）2、每個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（稱為頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域）tailvexheadvexHlinktlinkinfo頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)三、十字鏈表（自學(xué)）tailvex:弧尾頂點(diǎn)位置headvex:弧頭頂點(diǎn)位置hlink:弧頭相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息n個(gè)頂點(diǎn)—用順序存儲(chǔ)結(jié)構(gòu)data:存儲(chǔ)頂點(diǎn)信息。Firstin:以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)。Firstout:以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)。dataFirstinFirstout——適用于有向圖26第二十六頁(yè)，共四十一頁(yè)，2022年，8月28日0v11v22v33v4v1v2v3v4010^2202^^3例：畫出有向圖的十字鏈表。十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等?？臻g復(fù)雜度與鄰接表相同；建立的時(shí)間復(fù)雜度與鄰接表相同。3^03^^13^^2^數(shù)組下標(biāo)不屬結(jié)點(diǎn)分量27第二十七頁(yè)，共四十一頁(yè)，2022年，8月28日這是無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)，無(wú)向圖應(yīng)采用此種結(jié)構(gòu)存儲(chǔ)。1、每條邊只對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（稱為邊結(jié)點(diǎn)），設(shè)立6個(gè)域；2、每個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（頂點(diǎn)結(jié)點(diǎn)），設(shè)立2個(gè)域；markivexilinkjvexjlinkinfo邊結(jié)點(diǎn)四、鄰接多重表（自學(xué)）mark：標(biāo)志域，如處理過(guò)或搜索過(guò)。ivex，jvex:頂點(diǎn)域，邊依附的兩個(gè)頂點(diǎn)位置。ilink:指向下一條依附頂點(diǎn)i的邊結(jié)點(diǎn)位置。jlink;指向下一條依附頂點(diǎn)j的邊結(jié)點(diǎn)位置。info:邊信息，如權(quán)值等。n個(gè)頂點(diǎn)——用順序存儲(chǔ)結(jié)構(gòu)data:存儲(chǔ)頂點(diǎn)信息。Firstedge:依附頂點(diǎn)的第一條邊結(jié)點(diǎn)。dataFirstedge頂點(diǎn)結(jié)點(diǎn)——適用于無(wú)向圖28第二十八頁(yè)，共四十一頁(yè)，2022年，8月28日0v11v22v33v44v501^…0312^1423^24^3^4v1v2v3v5v4v4例：畫出無(wú)向圖的鄰接多重表鄰接多重表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的度等?？臻g復(fù)雜度與鄰接表相同；建立的時(shí)間復(fù)雜度與鄰接表相同。數(shù)組下標(biāo)不屬結(jié)點(diǎn)分量29第二十九頁(yè)，共四十一頁(yè)，2022年，8月28日一.深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V77.3圖的遍歷30第三十頁(yè)，共四十一頁(yè)，2022年，8月28日V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V531第三十一頁(yè)，共四十一頁(yè)，2022年，8月28日深度優(yōu)先遍歷算法算法P150~152算法7-1，7-2開始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問(wèn)過(guò)結(jié)束NYNYDFS開始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi==Vexnums結(jié)束NNYY32第三十二頁(yè)，共四十一頁(yè)，2022年，8月28日V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V433第三十三頁(yè)，共四十一頁(yè)，2022年，8月28日V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V534第三十四頁(yè)，共四十一頁(yè)，2022年，8月28日二.廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V0的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V835第三十五頁(yè)，共四十一頁(yè)，2022年，8月28日V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例廣度遍歷：V1V2