資源簡(jiǎn)介

(共66張PPT)
第5章 章 圖
圖的基本概念
圖的存儲(chǔ)
圖的創(chuàng)建
圖的遍歷
圖的基本概念
圖的存儲(chǔ)
圖的創(chuàng)建
5.2
5.3
5.1
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
圖的遍歷
5.4
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
學(xué)習(xí)目標(biāo)
掌握
掌握
掌握
掌握
掌握?qǐng)D的基本概念與專業(yè)術(shù)語
1
掌握編寫圖的操作代碼
4
2
掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)
3
掌握?qǐng)D的創(chuàng)建方法與遍歷方法
本章將介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)——圖。圖在高級(jí)嵌入式系統(tǒng)中應(yīng)用非常廣泛，車載GPS導(dǎo)航系統(tǒng)就是圖的典型應(yīng)用實(shí)例。圖形結(jié)構(gòu)相較于樹形結(jié)構(gòu)要更加復(fù)雜，樹形結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多的關(guān)系，而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的。本章將從圖的概念與專業(yè)術(shù)語開始介紹，重點(diǎn)講解圖的存儲(chǔ)結(jié)構(gòu)以及通過代碼實(shí)現(xiàn)圖的基本操作，包括創(chuàng)建、遍歷等。
5.1 圖的基本概念
5.1.1
圖的定義
返回目錄
5.1.2
圖的基本術(shù)語
5.1.1 圖的定義
在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，每個(gè)結(jié)點(diǎn)都可以有任意個(gè)前驅(qū)或后繼。換一種方式說，圖是由任意個(gè)頂點(diǎn)和任意條邊組成的結(jié)構(gòu)，頂點(diǎn)可以看作數(shù)據(jù)元素，邊是數(shù)據(jù)元素之間存在的關(guān)系。
圖的形式化定義為 G=(V,E)，其中：G表示一個(gè)圖，V表示圖中頂點(diǎn)的集合，E表示圖中邊（頂點(diǎn)間的關(guān)系）的集合。圖的邏輯結(jié)構(gòu)如圖所示。
圖中，頂點(diǎn)共有9個(gè)，即 V={A,B,C,D, E,F,G,H,I}，邊共有14條，即 E={AB,AC,AD,BD, BE,CD,CG,CF,DG,DH,DE,EI,GH,HI}。
5.1.2 圖的基本術(shù)語
1.無向圖
如果頂點(diǎn) V i 到頂點(diǎn) V j 之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對(duì)(V i ,V j )來表示。如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。如圖所示。
在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。含有n個(gè)頂點(diǎn)的無向完全圖有 條邊。如圖所示。
5.1.2 圖的基本術(shù)語
2.有向圖
如果頂點(diǎn)V i 到頂點(diǎn) V j 之間的邊有方向，則稱這條邊為有向邊（也可以稱為弧），從頂點(diǎn)V i 到頂點(diǎn) V j 的有向邊用有序偶對(duì)來表示。V i 稱為弧尾，V j 稱為弧頭。如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。如圖所示。
在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。含有n個(gè)頂點(diǎn)的有向完全圖有 n×（n－1）條邊。如圖所示。
5.1.2 圖的基本術(shù)語
在有向圖中，如不存在頂點(diǎn)到自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。圖所示為非簡(jiǎn)單圖。（本章介紹的圖都是簡(jiǎn)單圖）
5.1.2 圖的基本術(shù)語
3.稀疏圖與稠密圖
有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。稀疏與稠密是相對(duì)模糊的概念，沒有具體的量化標(biāo)準(zhǔn)。如果圖的邊或弧具有與其相關(guān)的數(shù)字，則將這些數(shù)字稱為權(quán)。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離。這種帶權(quán)的圖通常稱為網(wǎng)，如圖所示。
5.1.2 圖的基本術(shù)語
4.子圖
如果存在兩個(gè)圖G=(V,E)和 G'=(V',E')，并且滿足 V' V 和 E' E，則稱 G'為G的子圖。圖（b）、圖（c）、圖（d）都是圖（a）的子圖。
5.1.2 圖的基本術(shù)語
5.頂點(diǎn)的度
對(duì)于無向圖來說，某一個(gè)頂點(diǎn)的度是與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)量。如圖所示，頂點(diǎn)A的度為3，表示為 D(A)=3；頂點(diǎn)B的度為2，表示為 D(B)=2。
對(duì)于有向圖來說，以頂點(diǎn)V i 為弧頭的弧的數(shù)量稱為 V i 的入度，以頂點(diǎn) V i 為弧尾的弧的數(shù)量稱為V i 的出度，V i 的度為入度與出度的和。如圖所示，頂點(diǎn)C的入度為2，出度為2，度為4；頂點(diǎn)F的入度為1，度為1。
5.1.2 圖的基本術(shù)語
6.路徑
從頂點(diǎn) V i 到頂點(diǎn) V j 經(jīng)過的頂點(diǎn)與弧稱為 V i 與 V j 之間的路徑。對(duì)于有向圖來說，其路徑也是有向的。路徑上弧的數(shù)量稱為路徑的長(zhǎng)度。例如，圖中的頂點(diǎn)E到頂點(diǎn)F的路徑長(zhǎng)度為3或4。
如果路徑中的頂點(diǎn)不重復(fù)出現(xiàn)，則稱該路徑為簡(jiǎn)單路徑。第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)。除了第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。
圖中，B→C→A、E→B→C→F都是簡(jiǎn)單路徑；B→C→A→B為簡(jiǎn)單回路。
7.連通性
如果頂點(diǎn) V i 與頂點(diǎn) V j 之間存在路徑，則稱 V i 與 V j 是連通的。若圖中任意兩頂點(diǎn)都連通，則稱該圖為連通圖。在有向圖中，任意一對(duì)頂點(diǎn) V i 與 V j ，從 V i 到 V j 和從 V j 到 V i 都存在路徑，則稱該有向圖為強(qiáng)連通圖。
5.2 圖的存儲(chǔ)
5.2.1
鄰接矩陣
返回目錄
5.2.2
鄰接表
5.2.3
十字鏈表
5.2.4
鄰接多重表
5.2 圖的存儲(chǔ)
圖形結(jié)構(gòu)的存儲(chǔ)涉及兩部分內(nèi)容：頂點(diǎn)（數(shù)據(jù)元素）的信息與頂點(diǎn)之間的關(guān)系（邊或弧的信息）。本節(jié)將介紹4種存儲(chǔ)圖形結(jié)構(gòu)的方法，分別為鄰接矩陣、鄰接表、十字鏈表、鄰接多重表。
5.2.1 鄰接矩陣
鄰接矩陣使用兩個(gè)數(shù)組（一個(gè)一維數(shù)組與一個(gè)二維數(shù)組）來表示圖形結(jié)構(gòu)，一維數(shù)組用來存儲(chǔ)圖中頂點(diǎn)的信息，二維數(shù)組用來存儲(chǔ)圖中弧的信息。
假設(shè)圖G有n個(gè)頂點(diǎn)，則需要?jiǎng)?chuàng)建一個(gè)可以存儲(chǔ)n個(gè)數(shù)據(jù)元素的一維數(shù)組V[n]，并且創(chuàng)建一個(gè)可以存儲(chǔ) n×n 個(gè)數(shù)據(jù)元素的二維數(shù)組arc[n][n]，也可以將二維數(shù)組理解為一個(gè) n×n 的矩陣，其定義如下。
5.2.1 鄰接矩陣
上述公式中，1 表示頂點(diǎn) V i 與頂點(diǎn) V j 之間存在弧，0 表示不存在弧。
如圖所示，創(chuàng)建一個(gè)無向圖，并使用一維數(shù)組存儲(chǔ)頂點(diǎn)信息，使用二維數(shù)組（矩陣）表示頂點(diǎn)之間的關(guān)系。
5.2.1 鄰接矩陣
圖所示，存放圖頂點(diǎn)數(shù)據(jù)的數(shù)組為V[4]={A,B,C,D}，二維數(shù)組arc[4][4]對(duì)應(yīng)圖中的矩陣，由此可知，arc[2][0]=1表示的是頂點(diǎn)A與頂點(diǎn)C之間存在弧，arc[3][2]=1表示的是頂點(diǎn)C與頂點(diǎn)D之間存在弧。
如果圖為有向圖，則表示方法與無向圖類似，如圖所示，同樣使用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，使用二維數(shù)組存儲(chǔ)頂點(diǎn)之間的關(guān)系。
圖中，arc[3][0]=1表示從頂點(diǎn)D到頂點(diǎn)A具有弧，而arc[0][3]=0表示從頂點(diǎn)A到頂點(diǎn)D不具有弧。矩陣最后一行與最后一列表示頂點(diǎn)D的出度與入度，可知頂點(diǎn)D的度為3。
5.2.2 鄰接表
雖然鄰接矩陣可以解決圖形結(jié)構(gòu)的邏輯存儲(chǔ)問題，但是當(dāng)圖中的弧明顯少于頂點(diǎn)時(shí)，采用這種存儲(chǔ)方式會(huì)浪費(fèi)大量的存儲(chǔ)空間。
如圖所示，無向圖中的大部分頂點(diǎn)之間不存在連接關(guān)系，而二維數(shù)組本身占用的存儲(chǔ)空間不會(huì)隨著記錄信息的減少而減少。因此，使用二維數(shù)組記錄頂點(diǎn)關(guān)系，可能會(huì)造成大量存儲(chǔ)資源浪費(fèi)。
5.2.2 鄰接表
由線性表的存儲(chǔ)方式（第2章）可知，順序存儲(chǔ)（一維數(shù)組）由于預(yù)先分配內(nèi)存可能會(huì)造成存儲(chǔ)資源浪費(fèi)，而采用鏈?zhǔn)酱鎯?chǔ)則很好地解決了這一問題。圖形結(jié)構(gòu)同樣可以采用鏈?zhǔn)酱鎯?chǔ)的方式記錄頂點(diǎn)關(guān)系，這種方式稱為鄰接表。
鄰接表使用數(shù)組與鏈表結(jié)合的方式表示圖形結(jié)構(gòu)。使用一維數(shù)組存儲(chǔ)頂點(diǎn)信息，使用鏈表存儲(chǔ)頂點(diǎn)之間的關(guān)系。在一維數(shù)組中，每個(gè)數(shù)據(jù)元素分為兩部分，一部分為頂點(diǎn)數(shù)據(jù)，另一部分為指針。指針用來指向一個(gè)鏈表，該鏈表用來記錄當(dāng)前頂點(diǎn)的鄰接點(diǎn)的信息。因?yàn)猷徑狱c(diǎn)的數(shù)量不固定，所以鏈表的長(zhǎng)度也是不固定的。
使用鄰接表表示無向圖，如圖所示。
5.2.2 鄰接表
圖所示，一維數(shù)組中的每一個(gè)數(shù)據(jù)元素由data和ver組成。data中存儲(chǔ)的是頂點(diǎn)的數(shù)據(jù)，ver中存儲(chǔ)的是指針，該指針指向一個(gè)鏈表，鏈表中的結(jié)點(diǎn)存儲(chǔ)的是當(dāng)前頂點(diǎn)的鄰接點(diǎn)的下標(biāo)。其中，adj表示鄰接點(diǎn)在一維數(shù)組中的下標(biāo)，next用來指向下一個(gè)鄰接點(diǎn)。
圖中無向圖的頂點(diǎn)B，與其鄰接的是頂點(diǎn)A與頂點(diǎn)C，而頂點(diǎn)A與頂點(diǎn)C在一維數(shù)組中的下標(biāo)分別為0、2，因此頂點(diǎn)B對(duì)應(yīng)的ver指向的鏈表中有兩個(gè)結(jié)點(diǎn)，分別存儲(chǔ)的值為0、2。
如果圖是有向圖，其鄰接表的結(jié)構(gòu)也是類似的。由于有向圖的弧是有方向的，因此既需要記錄以頂點(diǎn)為弧頭的弧，也需要記錄以頂點(diǎn)為弧尾的弧。使用鄰接表的方式表示有向圖，如圖所示。
5.2.2 鄰接表
圖所示，鄰接表中的adj存儲(chǔ)的是某一頂點(diǎn)（該頂點(diǎn)為弧尾，出度）的鄰接點(diǎn)在一維數(shù)組中的下標(biāo)。逆鄰接表與鄰接表相反，adj存儲(chǔ)的是作為弧頭（入度）的頂點(diǎn)的鄰接點(diǎn)所在的下標(biāo)。由圖可知，頂點(diǎn)B為弧尾，鄰接點(diǎn)為頂點(diǎn)A與頂點(diǎn)C，頂點(diǎn)A與頂點(diǎn)C在一維數(shù)組中的下標(biāo)分別為0、2。頂點(diǎn)B為弧頭，鄰接點(diǎn)為頂點(diǎn)C，鄰接點(diǎn)在一維數(shù)組中的下標(biāo)為2。
如果圖中頂點(diǎn)之間的關(guān)系具有權(quán)值，則需要在鄰接表中添加一個(gè)記錄權(quán)值的數(shù)據(jù)域，如圖所示。
圖中，頂點(diǎn)C為弧尾時(shí)，其鄰接點(diǎn)為頂點(diǎn)A與頂點(diǎn)D，對(duì)應(yīng)的權(quán)值為15與13。
5.2.3 十字鏈表
對(duì)于有向圖而言，鄰接表具有一定的缺陷。如圖所示，鄰接表只能解決頂點(diǎn)出度的問題，而逆鄰接表只能解決頂點(diǎn)入度的問題。因此，可以考慮將鄰接表與逆鄰接表結(jié)合到一起，這種存儲(chǔ)方式就是十字鏈表。
十字鏈表與鄰接表都采用了數(shù)組與鏈表結(jié)合的方式來表示圖形結(jié)構(gòu)。十字鏈表相對(duì)于鄰接表而言，數(shù)據(jù)的結(jié)構(gòu)更加復(fù)雜。其中，一維數(shù)組中的數(shù)據(jù)元素的結(jié)構(gòu)如圖所示。
圖中，data表示有向圖中頂點(diǎn)的數(shù)據(jù)，in表示指針，指向以該頂點(diǎn)為弧頭的鄰接點(diǎn)的記錄（即鏈表中的結(jié)點(diǎn)），out同樣為指針，指向以該頂點(diǎn)為弧尾的鄰結(jié)點(diǎn)的記錄（即鏈表中的結(jié)點(diǎn)）。
5.2.3 十字鏈表
鏈表中的結(jié)點(diǎn)保存的是鄰接點(diǎn)的記錄，其結(jié)構(gòu)如圖所示。
圖中，tail表示弧尾頂點(diǎn)在數(shù)組中的下標(biāo)，head表示弧頭頂點(diǎn)在數(shù)組中的下標(biāo)，headlink為指針，指向以頂點(diǎn)為弧頭的下一個(gè)鄰接點(diǎn)的記錄，taillink同樣為指針，指向以頂點(diǎn)為弧尾的下一個(gè)鄰接點(diǎn)的記錄。
假設(shè)存在一個(gè)有向圖，使用十字鏈表表示該有向圖，如圖所示。
5.2.3 十字鏈表
頂點(diǎn) A 作為弧尾時(shí)，鄰接點(diǎn)為頂點(diǎn) D，而作為弧頭時(shí)，鄰接點(diǎn)為頂點(diǎn) B 與頂點(diǎn) C。因此，頂點(diǎn) A的 in 指向的結(jié)點(diǎn)中，tail 值為 1（即鄰接點(diǎn) B 的數(shù)組下標(biāo)），head 值為 0（即頂點(diǎn) A 的數(shù)組下標(biāo)），headlink 指向下一個(gè)鄰接點(diǎn)的記錄，其 tail 值為 2（即鄰接點(diǎn) C 的數(shù)組下標(biāo)），head 值為 0（即頂點(diǎn) A的數(shù)組下標(biāo)）。頂點(diǎn) A 的 out 指向的結(jié)點(diǎn)中，tail 值為 0（即頂點(diǎn) A 的數(shù)組下標(biāo)），head 值為 3（即鄰接點(diǎn) D 的數(shù)組下標(biāo)）。
頂點(diǎn) B 作為弧尾時(shí)，鄰接點(diǎn)為頂點(diǎn) A 與頂點(diǎn) C，而作為弧頭時(shí)，鄰接點(diǎn)為頂點(diǎn) C。因此，頂點(diǎn) B的 in 指向的結(jié)點(diǎn)中，tail 值為 2（即鄰接點(diǎn) C 的數(shù)組下標(biāo)），head 值為 1（即頂點(diǎn) B 的數(shù)組下標(biāo)）。頂點(diǎn) B 的 out 指向的結(jié)點(diǎn)中，tail 值為 1（即頂點(diǎn) B 的數(shù)組下標(biāo)），head 值為 0（即鄰接點(diǎn) A 的數(shù)組下標(biāo)），taillink 指向下一個(gè)鄰接點(diǎn)的記錄，其 tail 值為 1（即頂點(diǎn) B 的數(shù)組下標(biāo)），head 值為 2（即鄰接點(diǎn) C 的數(shù)組下標(biāo)）
頂點(diǎn) C 與頂點(diǎn) D 的情況可參考上述分析，這里不再詳細(xì)描述。十字鏈表的優(yōu)勢(shì)就是將鄰接表與逆鄰接表進(jìn)行了結(jié)合。由圖 5.19 可以看出，十字鏈表的本質(zhì)是鏈表交叉，即同一個(gè)結(jié)點(diǎn)可以存在于多條鏈表中。
5.2.4 鄰接多重表
鄰接多重表與鄰接表類似，不同的是，鄰接多重表重點(diǎn)關(guān)注的是頂點(diǎn)之間的關(guān)系（邊或弧），而非頂點(diǎn)。使用鄰接表表示無向圖時(shí)，如果選擇操作圖中的某一條邊，則需要找到這條邊的兩個(gè)頂點(diǎn)在鄰接表中的信息，然后才能進(jìn)行操作。如果當(dāng)前需要頻繁地處理頂點(diǎn)之間的關(guān)系，那么使用鄰接表表示圖形結(jié)構(gòu)并不是一個(gè)很好的選擇。
鄰接多重表使用數(shù)組與鏈表結(jié)合的方式表示圖形結(jié)構(gòu)，其不同于鄰接表的是，鏈表中的結(jié)點(diǎn)表示的是與頂點(diǎn)相關(guān)聯(lián)的邊，而非頂點(diǎn)。鄰接多重表中結(jié)點(diǎn)的結(jié)構(gòu)如圖所示。
圖中，iver與jver表示與邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)在數(shù)組中的下標(biāo)，ilink指向與頂點(diǎn)iver相關(guān)聯(lián)的下一條邊的記錄（下一個(gè)鏈表結(jié)點(diǎn)），jlink指向與頂點(diǎn)jver相關(guān)聯(lián)的下一條邊的記錄（下一個(gè)鏈表結(jié)點(diǎn)）。
5.2.4 鄰接多重表
使用鄰接多重表表示無向圖如圖所示。
5.2.4 鄰接多重表
圖所示，與頂點(diǎn)A相關(guān)聯(lián)的邊有3條，分別為(A,B)、(A,C)、(A,D)。如果轉(zhuǎn)換為用數(shù)據(jù)下標(biāo)表示，則分別為(0,1)、(0,2)、(0,3)。因此，頂點(diǎn)A的ver指向的結(jié)點(diǎn)中，iver為0（頂點(diǎn)A），jver為1（頂點(diǎn)B），且ilink指向下一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的jver為0（頂點(diǎn)A），iver為3（頂點(diǎn)D），jlink指向下一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的iver為0，jver為2。
鄰接多重表與鄰接表類似，鄰接表關(guān)注的是頂點(diǎn)的信息，而鄰接多重表關(guān)注的是頂點(diǎn)之間（的關(guān)系邊或弧）。
5.3 圖的創(chuàng)建
5.3.1
定義圖形結(jié)構(gòu)
返回目錄
5.3.2
創(chuàng)建圖形結(jié)構(gòu)
5.3.3
確定頂點(diǎn)關(guān)系
5.3.4
輸出頂點(diǎn)關(guān)系
5.3.5
整體測(cè)試
5.3 圖的創(chuàng)建
5.2節(jié)主要介紹了如何實(shí)現(xiàn)圖形結(jié)構(gòu)的存儲(chǔ)，即圖形結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法。本節(jié)將通過具體的代碼實(shí)現(xiàn)圖形結(jié)構(gòu)的創(chuàng)建以及操作。
5.3.1 定義圖形結(jié)構(gòu)
下面展示通過鄰接矩陣的方式對(duì)圖形結(jié)構(gòu)進(jìn)行定義。鄰接矩陣采用一維數(shù)組與二維數(shù)組組合的方式表示圖形結(jié)構(gòu)。因此，通過代碼實(shí)現(xiàn)對(duì)圖形結(jié)構(gòu)的定義如下所示。
以上述定義通過結(jié)構(gòu)體將一維數(shù)組與二維數(shù)組組合在一起表示圖形結(jié)構(gòu)。如果采用5.2節(jié)中介紹的其他方式表示圖形結(jié)構(gòu)，只需將結(jié)構(gòu)體中的二維數(shù)組替換成其他結(jié)構(gòu)即可。
5.3.2 創(chuàng)建圖形結(jié)構(gòu)
下面展示通過鄰接矩陣的方式創(chuàng)建無向圖，具體代碼如下。（變量定義與5.3.1節(jié)一致）。
以上代碼使用malloc()函數(shù)為結(jié)構(gòu)體申請(qǐng)內(nèi)存空間，對(duì)結(jié)構(gòu)體中的一維數(shù)組賦值就是向頂點(diǎn)中保存數(shù)據(jù)。需要特別注意的是，該函數(shù)并未確定圖中頂點(diǎn)之間的關(guān)系。
5.3.3 確定頂點(diǎn)關(guān)系
確定圖中頂點(diǎn)之間的關(guān)系需要對(duì)二維數(shù)組賦值，假設(shè)數(shù)字1表示頂點(diǎn)之間存在關(guān)系（頂點(diǎn)之間存在弧），數(shù)字0表示頂點(diǎn)之間不存在關(guān)系。具體代碼如下。（變量定義與5.3.1節(jié)一致）。
以上代碼通過函數(shù)scanf()讀取終端輸入，輸入內(nèi)容為二維數(shù)組的坐標(biāo)。賦值為1，表示存在關(guān)系。
5.3.4 輸出頂點(diǎn)關(guān)系
輸出頂點(diǎn)關(guān)系即輸出二維數(shù)組中的數(shù)據(jù)，通過數(shù)據(jù)可以判定無向圖中頂點(diǎn)之間的關(guān)系。具體代碼如下所示。（變量定義與5.3.1節(jié)一致）。
以上代碼遍歷整個(gè)二維數(shù)組，通過某一個(gè)結(jié)點(diǎn)的值，即可推出頂點(diǎn)之間是否存在弧。例如，matrix[1][2]=1表示一維數(shù)組中保存的第2個(gè)頂點(diǎn)與第3個(gè)頂點(diǎn)之間存在弧。
5.3.5 整體測(cè)試
對(duì)5.3.1節(jié)至5.3.4節(jié)的功能代碼進(jìn)行整體測(cè)試，示例代碼參考教材5.3.5節(jié)。
例中，主函數(shù)調(diào)用子函數(shù)完成圖的創(chuàng)建，然后執(zhí)行確定頂點(diǎn)關(guān)系的函數(shù)，最后輸出圖中頂點(diǎn)的關(guān)系。程序運(yùn)行結(jié)果如下所示。
5.3.5 整體測(cè)試
運(yùn)行程序，按照格式輸入坐標(biāo)值，當(dāng)輸入格式錯(cuò)誤的內(nèi)容時(shí)，程序自動(dòng)結(jié)束讀取。根據(jù)輸出內(nèi)容可知，具有關(guān)系的邊有(V 0 ,V 1 )、(V 0 ,V 2 )、(V 0 ,V 3 )、(V 1 ,V 2 )、(V 1 ,V 3 )、(V 2 ,V 3 )、(V 2 ,V 4 )、(V 3 ,V 4 )。因此，根據(jù)輸入的頂點(diǎn)數(shù)據(jù)與關(guān)系，可以確定程序創(chuàng)建的無向圖的邏輯結(jié)構(gòu)，如圖所示。
5.4 圖的遍歷
5.4.1
深度優(yōu)先搜索
返回目錄
5.4.2
廣度優(yōu)先搜索
5.4.3
最短路徑
5.4 圖的遍歷
圖的遍歷與樹的遍歷類似，即從圖中的某個(gè)頂點(diǎn)開始，經(jīng)過一定的路線訪問圖中所有可以訪問的頂點(diǎn)，并且這些頂點(diǎn)只能被訪問一次，這個(gè)過程稱為圖的遍歷。圖的遍歷方式通常可以分為深度優(yōu)先搜索與廣度優(yōu)先搜索兩種。
5.4.1 深度優(yōu)先搜索
1.深度優(yōu)先搜索的概念
深度優(yōu)先搜索（Depth First Search，DFS）類似于樹的先序遍歷。從圖中的某個(gè)頂點(diǎn)開始訪問，訪問完成后，需要按照深度優(yōu)先的原則，繼續(xù)訪問其鄰接點(diǎn)，并以此類推。若某頂點(diǎn)的鄰接點(diǎn)全部訪問完畢，則回溯到它的上一個(gè)頂點(diǎn)，然后從此頂點(diǎn)開始，按照深度優(yōu)先的原則繼續(xù)搜索，直到可以被訪問的頂點(diǎn)都訪問完畢為止。
如圖所示，假設(shè)從無向圖中的頂點(diǎn)A開始訪問，定義一個(gè)訪問規(guī)則（參考樹的先序遍歷）：訪問頂點(diǎn)的下一個(gè)鄰接點(diǎn)時(shí)，首先訪問頂點(diǎn)右邊（頂點(diǎn)角度）的鄰接點(diǎn)。
5.4.1 深度優(yōu)先搜索
圖 中，按照先訪問頂點(diǎn)右邊的鄰接點(diǎn)的規(guī)則，從訪問頂點(diǎn) A開始，頂點(diǎn) A 的鄰接點(diǎn)有 B、F，應(yīng)該先訪問頂點(diǎn) B。頂點(diǎn) B 的鄰接點(diǎn)有 C、G、H，應(yīng)該先訪問頂點(diǎn) C。頂點(diǎn) C 的鄰接點(diǎn)有 B、G、D，應(yīng)該先訪問頂點(diǎn) D。頂點(diǎn) D 的鄰接點(diǎn)有 C、G、H、I、E，應(yīng)該先訪問頂點(diǎn) E。頂點(diǎn) E 的鄰接點(diǎn)有 D、I、F，應(yīng)該先訪問頂點(diǎn) F。頂點(diǎn) F的鄰接點(diǎn)有 A、H、I、E，因?yàn)轫旤c(diǎn) A 已經(jīng)被訪問，所以應(yīng)該先訪問頂點(diǎn) H。頂點(diǎn) H 的鄰接點(diǎn)為 B、D、I、F，其中頂點(diǎn) B、D、F 都已經(jīng)被訪問，因此只能訪問頂點(diǎn) I。經(jīng)過上述遍歷后，可以發(fā)現(xiàn)頂點(diǎn)G 并沒有被訪問，因此在訪問到 I 時(shí)，遍歷并沒有結(jié)束，而需要按照原來訪問的路徑返回。當(dāng)返回到頂點(diǎn) D 時(shí)，鄰接點(diǎn) C、H、I 都已經(jīng)被訪問，只剩下頂點(diǎn) G 未被訪問。頂點(diǎn) G 訪問完成后，繼續(xù)返回，直到返回到頂點(diǎn) A 停止。
綜上所述，圖中頂點(diǎn)的訪問順序?yàn)?A-B-C-D-E-F-H-I-G。由上述遍歷過程可以看出，該遍歷方式與樹的遍歷一樣，需要借助遞歸的方式實(shí)現(xiàn)。
5.4.1 深度優(yōu)先搜索
2.深度優(yōu)先搜索的實(shí)現(xiàn)
下面介紹基于鄰接矩陣存儲(chǔ)方式的深度優(yōu)先搜索，其核心操作為采用遞歸調(diào)用的思想尋找頂點(diǎn)的鄰接點(diǎn)。如果某個(gè)頂點(diǎn)的所有鄰接點(diǎn)都已經(jīng)被訪問，則返回到上一個(gè)頂點(diǎn)，繼續(xù)訪問。具體代碼如下所示。（變量定義與5.3.1節(jié)一致）。
5.4.1 深度優(yōu)先搜索
5.4.1 深度優(yōu)先搜索
以上代碼中采用遞歸調(diào)用的方式，依次尋找頂點(diǎn)的鄰接點(diǎn)。其設(shè)計(jì)思想如圖所示。
graph_DFS()函數(shù)的功能為輸出頂點(diǎn)數(shù)據(jù)，并調(diào)用graph_adj()函數(shù)尋找頂點(diǎn)的鄰接點(diǎn)。
5.4.1 深度優(yōu)先搜索
3.整體測(cè)試
整體測(cè)試需要結(jié)合鄰接矩陣存儲(chǔ)圖形結(jié)構(gòu)的代碼（例5-1），示例代碼參考教材5.4.1節(jié)。
例中，主函數(shù)調(diào)用子函數(shù)創(chuàng)建圖，并需要終端輸入頂點(diǎn)關(guān)系，通過深度優(yōu)先搜索函數(shù)輸出訪問結(jié)果。程序運(yùn)行結(jié)果如下所示。
5.4.1 深度優(yōu)先搜索
5.4.1 深度優(yōu)先搜索
無向圖中的頂點(diǎn)共有 9 個(gè)，根據(jù)輸入的頂點(diǎn)數(shù)據(jù)與關(guān)系，可以確定程序創(chuàng)建的無向圖的邏輯結(jié)構(gòu)，如圖 所示。
例輸出的搜索結(jié)果為 0–1–2–3–4–5–7–8–6，結(jié)合圖 5.25 可知，運(yùn)算結(jié)果與推理一致，深度搜索成功。
5.4.2 廣告優(yōu)先搜索
1.廣度優(yōu)先搜索的概念
廣度優(yōu)先搜索（Breadth First Search，BFS）類似于樹的層序遍歷,。例如，5.4.1節(jié)中的圖5.23中，從頂點(diǎn)A開始訪問（頂點(diǎn)A作為層序遍歷的第一層）；頂點(diǎn)A的鄰接點(diǎn)為頂點(diǎn)B、頂點(diǎn)F，因此將頂點(diǎn)B、頂點(diǎn)F作為層序遍歷的第二層，其鄰接點(diǎn)為C、G、H、E；同樣將頂點(diǎn)C、頂點(diǎn)G、頂點(diǎn)H、頂點(diǎn)E作為層序遍歷的第三層，其鄰接點(diǎn)為頂點(diǎn)D、頂點(diǎn)I（頂點(diǎn)D、I作為遍歷的第四層）。將圖按照層序遍歷的思想重新設(shè)計(jì)，如圖所示。
5.4.2 廣告優(yōu)先搜索
無論是樹還是圖，層序遍歷都需要借助于隊(duì)列來完成（隊(duì)列實(shí)現(xiàn)數(shù)據(jù)先進(jìn)先出）。圖中，第一層為頂點(diǎn)A，第二層為頂點(diǎn)B、頂點(diǎn)F，第三層為頂點(diǎn)C、頂點(diǎn)G、頂點(diǎn)H、頂點(diǎn)E，第四層為頂點(diǎn)D、頂點(diǎn)I。因此，通過隊(duì)列實(shí)現(xiàn)遍歷的原理如圖所示。
5.4.2 廣告優(yōu)先搜索
圖所示原理為：將無向圖中每一層的頂點(diǎn)按照順序入隊(duì)、出隊(duì)，并訪問數(shù)據(jù)。廣度優(yōu)先搜索即每次必須先找到頂點(diǎn)的所有鄰接點(diǎn)，訪問完成后，再尋找這些鄰接點(diǎn)的下一層鄰接點(diǎn)。
2. 廣度優(yōu)先搜索的實(shí)現(xiàn)
下面介紹基于鄰接矩陣存儲(chǔ)方式的廣度優(yōu)先搜索，具體代碼如下所示。（隊(duì)列函數(shù)實(shí)現(xiàn)可參考3.6節(jié)鏈?zhǔn)疥?duì)列的代碼實(shí)現(xiàn)）。
5.4.2 廣告優(yōu)先搜索
以上代碼實(shí)現(xiàn)的原理如圖所示。
5.4.2 廣告優(yōu)先搜索
3.整體測(cè)試
整體測(cè)試需要結(jié)合鄰接矩陣存儲(chǔ)圖形結(jié)構(gòu)的代碼（例5-1）以及3.6節(jié)鏈?zhǔn)疥?duì)列的操作代碼。首先將鏈?zhǔn)疥?duì)列的操作代碼直接封裝為頭文件，然后使用操作圖形結(jié)構(gòu)的代碼調(diào)用該頭文件，即可完成測(cè)試。
鏈?zhǔn)疥?duì)列的操作代碼，鏈?zhǔn)疥?duì)列的操作代碼參考教材5.4.2節(jié)。
廣度優(yōu)先搜索的代碼參考教材5.4.2節(jié)。
例中，主函數(shù)調(diào)用子函數(shù)完成圖的創(chuàng)建，然后執(zhí)行確定頂點(diǎn)關(guān)系的函數(shù)，最后輸出圖中頂點(diǎn)的關(guān)系。通過廣度優(yōu)先搜索函數(shù)實(shí)現(xiàn)遍歷，程序運(yùn)行結(jié)果如下所示。
5.4.2 廣告優(yōu)先搜索
5.4.2 廣告優(yōu)先搜索
無向圖中的頂點(diǎn)共有 9 個(gè)，根據(jù)輸入的頂點(diǎn)數(shù)據(jù)與關(guān)系，可以確定程序創(chuàng)建的無向圖的邏輯結(jié)構(gòu)與 5.4.1 節(jié)中的圖 5.25 一致。其中，頂點(diǎn) V 0 的鄰接點(diǎn)為頂點(diǎn) V 1 、頂點(diǎn) V 5 ，頂點(diǎn) V 1 、頂點(diǎn) V 5 的鄰接點(diǎn)為頂點(diǎn) V 2 、頂點(diǎn) V 4 、頂點(diǎn) V 6 、頂點(diǎn) V 7 ，頂點(diǎn) V 2 、頂點(diǎn) V 4 、頂點(diǎn) V 6 、頂點(diǎn) V 7 的鄰接點(diǎn)為頂點(diǎn) V 3 、頂點(diǎn) V 8 。按照層序遍歷的思想重新設(shè)計(jì)，如圖所示。
結(jié)合圖和廣度優(yōu)先搜索的規(guī)則，可以推理出頂點(diǎn)被訪問的 順 序 為 V 0 -V 1 -V 5 -V 2 -V 6 -V 7 -V 4 -V 3 -V 8 。 程 序 輸 出 的 結(jié) 果 為0–1–5–2–6–7–4–3–8。程序輸出結(jié)果與推理結(jié)果一致，表示廣度優(yōu)先搜索成功。
5.4.3 最短路徑
1．最短路徑的概念
在非網(wǎng)圖（邊或弧不具有權(quán)值）中，最短路徑指的是兩頂點(diǎn)之間經(jīng)過邊數(shù)最少的路徑。而在網(wǎng)圖（邊或弧具有權(quán)值）中，最短路徑指的是兩頂點(diǎn)之間經(jīng)過的邊的權(quán)值之和最小的路徑，路徑上的第一個(gè)頂點(diǎn)稱為源點(diǎn)，最后一個(gè)頂點(diǎn)稱為終點(diǎn)。
2．迪杰斯特拉算法
迪杰斯特拉（Dijkstra）算法是按照路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑的算法。迪杰斯特拉算法主要討論的是從一個(gè)頂點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑（也稱為單源最短路徑）。算法的基本思想為：將圖中的頂點(diǎn)分為兩個(gè)集合 S 和 T，集合 S 中存放已確定最短路徑的頂點(diǎn)，集合 T 中存放未確定最短路徑的頂點(diǎn)，按照最短路徑長(zhǎng)度遞增的次序?qū)⒓?T 中的頂點(diǎn)逐個(gè)加入集合 S，直到從源點(diǎn)出發(fā)可以到達(dá)的所有頂點(diǎn)都在集合 S 中。
5.4.3 最短路徑
如圖所示，創(chuàng)建一個(gè)具有權(quán)值的圖。接下來通過該圖形結(jié)構(gòu)對(duì)迪杰斯特拉算法的原理進(jìn)行分析。
（1）在集合 S 中加入頂點(diǎn) A，即 S=(A)，此時(shí)最短路徑為 A→A（權(quán)值為 0）。集合 T 中的頂點(diǎn)有 B、C、D、E、F，即 T=(B,C,D,E,F)。頂點(diǎn) A 的鄰接點(diǎn)為頂點(diǎn) B、頂點(diǎn) C，A→B 的權(quán)值為 6，A→C 的權(quán)值為 3，其中 A→C 的權(quán)值較小。
5.4.3 最短路徑
（2）在集合 S 中加入頂點(diǎn) C，即 S=(A,C)。集合 T 中的頂點(diǎn)有 B、D、E、F，即 T=(B,D,E,F)。頂
點(diǎn) C 的鄰接點(diǎn)有頂點(diǎn) A、頂點(diǎn) B、頂點(diǎn) D、頂點(diǎn) E，A→C→B 的權(quán)值為 5，A→C→D 的權(quán)值為 6，A→C→E的權(quán)值為 7，其中 A→C→B 的權(quán)值最小。
（3）在集合 S 中加入頂點(diǎn) B，即 S=(A,C,B)。集合 T 中的頂點(diǎn)有 D、E、F，即 T=(D,E,F)。頂點(diǎn) B的鄰接點(diǎn)有頂點(diǎn) A、頂點(diǎn) C、頂點(diǎn) D，A→C→B→D 的權(quán)值為 10，該權(quán)值大于上一步中 A→C→D 的權(quán)值。因此，這里需要變更為權(quán)值較小的路徑，即 A→C→D。
（4）在集合 S 中加入頂點(diǎn) D，即 S=(A,C,B,D)。集合 T 中的頂點(diǎn)有 E、F，即 T=(E,F)。頂點(diǎn) D 的鄰接點(diǎn)有頂點(diǎn) B、頂點(diǎn) C、頂點(diǎn) E、頂點(diǎn) F，A→C→D→E 的權(quán)值為 8，A→C→D→F 的權(quán)值為 9。路徑 A→C→D→E 的權(quán)值大于上一步中 A→C→E 的權(quán)值。因此，這里需要變更為權(quán)值較小的路徑，即A→C→E。
（5）在集合 S 中加入頂點(diǎn) E，即 S=(A,C,B,D,E)。集合 T 中的頂點(diǎn)有 F，即 T=(F)。頂點(diǎn) E 的鄰接點(diǎn)為頂點(diǎn) C、頂點(diǎn) D、頂點(diǎn) F，A→C→E→F 的權(quán)值為 12，該權(quán)值大于上一步中 A→C→D→F 的權(quán)值。因此，這里需要變更為權(quán)值較小的路徑，即 A→C→D→F。
5.4.3 最短路徑
（5）在集合 S 中加入頂點(diǎn) E，即 S=(A,C,B,D,E)。集合 T 中的頂點(diǎn)有 F，即 T=(F)。頂點(diǎn) E 的鄰接點(diǎn)為頂點(diǎn) C、頂點(diǎn) D、頂點(diǎn) F，A→C→E→F 的權(quán)值為 12，該權(quán)值大于上一步中 A→C→D→F 的權(quán)值。因此，這里需要變更為權(quán)值較小的路徑，即 A→C→D→F。
（6）在集合 S 中加入頂點(diǎn) F，即 S=(A,C,B,D,E,F)。集合 T 為空，查找完畢。頂點(diǎn) A 到頂點(diǎn) A 的最短路徑為 A→A（0），頂點(diǎn) A 到頂點(diǎn) B 的最短路徑為 A→C→B（5），頂點(diǎn) A 到頂點(diǎn) C 的最短路徑為
A→C（3），頂點(diǎn) A 到頂點(diǎn) D 的最短路徑為 A→C→D（6），頂點(diǎn) A 到頂點(diǎn) E 的最短路徑為 A→C→E（7），頂點(diǎn) A 到頂點(diǎn) F 的最短路徑為 A→C→D→F（9）。
由上述分析可知，通過迪杰斯特拉算法計(jì)算兩頂點(diǎn)之間的最短路徑并非一步完成，而是在已經(jīng)得出最短路徑的基礎(chǔ)上，求到更遠(yuǎn)頂點(diǎn)的最短路徑。上述操作中，按最短路徑長(zhǎng)度的遞增次序依次把集合 T 中的頂點(diǎn)加入集合 S。在加入的過程中，總保持從源點(diǎn) A 到集合 S 中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn) A 到集合 T 中任何頂點(diǎn)的最短路徑長(zhǎng)度。
5.4.3 最短路徑
3．弗洛伊德算法
如果每次以圖中的一個(gè)頂點(diǎn)（不重復(fù)）作為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法，便可求出每對(duì)頂點(diǎn)之間的最短路徑，但顯然這種處理方式是比較復(fù)雜的。接下來將介紹一種適合計(jì)算任意兩頂點(diǎn)之間的最短路徑的算法——弗洛伊德（Floyd）算法。
弗洛伊德算法的核心為：對(duì)于任意一對(duì)頂點(diǎn) V i 和 V j ，判斷是否存在一個(gè)頂點(diǎn) V x ，使得從頂點(diǎn) V i到頂點(diǎn) V x 再到頂點(diǎn) V j 比己知的路徑更短，如果存在，則更新該路徑。
如圖所示，創(chuàng)建一個(gè)有向圖。接下來通過該圖形結(jié)構(gòu)對(duì)弗洛伊德算法的原理進(jìn)行分析。
5.4.3 最短路徑
使用矩陣（二維數(shù)組E）表示圖中有向圖的頂點(diǎn)關(guān)系，如圖所示。
頂點(diǎn) A 到頂點(diǎn) B 的路徑為 2，則設(shè) E[0][1]=2。頂點(diǎn) C 到頂點(diǎn) B 不存在弧，則設(shè) E[2][1] =∞。頂?shù)?D 到頂點(diǎn) C 的路徑為 12，則設(shè) E[3][2]=12。
根據(jù)弗洛伊德算法的核心思想，如果需要將任意兩個(gè)頂點(diǎn)（例如，從頂點(diǎn) A 到頂點(diǎn) C）之間的路徑變短，則需要引入第三個(gè)頂點(diǎn)（假設(shè)為頂點(diǎn) K），并通過這個(gè)頂點(diǎn)中轉(zhuǎn)（即 A→K→C）。而有些時(shí)候需要經(jīng)過兩個(gè)或更多的頂點(diǎn)中轉(zhuǎn)才能使路徑變短，如 A→K→L→M→C。
5.4.3 最短路徑
圖中，從頂點(diǎn) D 到頂點(diǎn) C 的路徑權(quán)值為 12，如果通過頂點(diǎn) A 中轉(zhuǎn)（D A C），路徑將縮短為權(quán)值 11（E[3][0]+E[0][2]=5+6=11）。其中，頂點(diǎn) A 到頂點(diǎn) C 也可以通過頂點(diǎn) B 中轉(zhuǎn)，使得頂點(diǎn)A 到頂點(diǎn) C 的路徑縮短為權(quán)值 5（E[0][1]+E[1][2]=2+3=5）。因此，同時(shí)經(jīng)過頂點(diǎn) A 和頂點(diǎn) B 中轉(zhuǎn)，從頂點(diǎn) D 到頂點(diǎn) C 的路徑會(huì)進(jìn)一步縮短為權(quán)值 10。
圖中，如果任意兩個(gè)頂點(diǎn)之間不允許通過其他頂點(diǎn)中轉(zhuǎn)，那么頂點(diǎn)之間的最短路徑就是初始路徑，權(quán)值如圖 5.32 所示。如果只允許通過頂點(diǎn) A 進(jìn)行中轉(zhuǎn)，那么需要對(duì)任意兩點(diǎn)之間的最短路徑進(jìn)行更新，如圖所示。
5.4.3 最短路徑
圖中，頂點(diǎn) C 到頂點(diǎn) B 的路徑更新后權(quán)值為 9，即 E[2][1]=9，頂點(diǎn) D 到頂點(diǎn) B 的路徑更新后權(quán)值為 7，即 E[3][1]=7，頂點(diǎn) D 到頂點(diǎn) C 的路徑更新后權(quán)值為 11，即 E[3][2]=11。
如果允許通過頂點(diǎn) A 與頂點(diǎn) B 進(jìn)行中轉(zhuǎn)，那么需要對(duì)任意兩點(diǎn)之間的最短路徑再次進(jìn)行更新，如圖所示。
5.4.3 最短路徑
圖中，頂點(diǎn) A 到頂點(diǎn) C 的路徑更新后權(quán)值為 5，即 E[0][2]=5，頂點(diǎn) D 到頂點(diǎn) C 的路徑更新后權(quán)值為 10，即 E[3][2]=10。
如果允許通過頂點(diǎn) A、B、C 進(jìn)行中轉(zhuǎn)，那么需要對(duì)兩點(diǎn)之間的最短路徑再次進(jìn)行更新，如圖所示。
圖中，頂點(diǎn) B 到頂點(diǎn) A 的路徑更新后權(quán)值為 10，即 E[1][0]=10，頂點(diǎn) B 到頂點(diǎn) D 的路徑更新后權(quán)值為 4，即 E[1][3]=4。
5.4.3 最短路徑
如果允許通過所有頂點(diǎn)進(jìn)行中轉(zhuǎn)，那么需要對(duì)兩點(diǎn)之間的最短路徑再次進(jìn)行更新，如圖所示。
如圖中，頂點(diǎn)B到頂點(diǎn)A的路徑更新為9，即E[1][0]=9，頂點(diǎn)C到頂點(diǎn)A的路徑更新為6，即E[2][0]=6，頂點(diǎn)C到頂點(diǎn)B的路徑更新為8，即E[2][1]=8。
5.4.3 最短路徑
將圖與圖 5.32 進(jìn)行對(duì)比可以看出，通過逐個(gè)添加頂點(diǎn)中轉(zhuǎn)（弗洛伊德算法的核心），圖中部分頂點(diǎn)之間的路徑縮短。頂點(diǎn) A 到 C 的路徑更新后權(quán)值為 5（A→B→C），頂點(diǎn) B 到 A 的路徑更新后權(quán)值為 9（B→C→D→A），頂點(diǎn) B 到頂點(diǎn) D 的路徑更新后權(quán)值為 4（B→C→D），頂點(diǎn) C 到 A 的路徑更新后權(quán)值為 6（C→D→A），頂點(diǎn) C 到頂點(diǎn) B 的路徑更新后權(quán)值為 8（C→D→A→B），頂點(diǎn) D 到頂點(diǎn) B 的路徑更新后權(quán)值為 7（D→A→B），頂點(diǎn) D 到頂點(diǎn) C 的路徑更新后權(quán)值為 10（D→A→B→C）。圖中各頂點(diǎn)之間的路徑就是最短路徑。
本章小結(jié)
本章主要介紹了一種非線性數(shù)據(jù)結(jié)構(gòu)——圖，包括圖的基本概念、圖的存儲(chǔ)、圖的創(chuàng)建、圖的遍歷四個(gè)部分。其中，需要重點(diǎn)關(guān)注的是圖形結(jié)構(gòu)的存儲(chǔ)方法，即鄰接矩陣、鄰接表、十字鏈表、鄰接多重表。本章在最后展示了圖形結(jié)構(gòu)（基于鄰接矩陣表示）的操作代碼，包括圖的創(chuàng)建、圖的遍歷。圖的遍歷主要有深度優(yōu)先搜索與廣度優(yōu)先搜索。望讀者理解圖形結(jié)構(gòu)的存儲(chǔ)方法以及圖的遍歷，熟練編寫操作代碼。

展開更多......

收起↑