2018年國(guó)家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(14)

重點(diǎn)需要解釋虛線(xiàn)箭頭的含義。它其實(shí)就是此圖的逆鄰接表的表示。對(duì)于v0來(lái)說(shuō)，它有兩個(gè)頂點(diǎn)v1和v2的入邊。因此的firstin指向頂點(diǎn)v1的邊表結(jié)點(diǎn)中headvex為0的結(jié)點(diǎn)，如上圖圓圈1。接著由入邊結(jié)點(diǎn)的headlink指向下一個(gè)入邊頂點(diǎn)v2，如上圖圓圈2。對(duì)于頂點(diǎn)v1，它有一個(gè)入邊頂點(diǎn)v2，所以它的firstin指向頂點(diǎn)v2的邊表結(jié)點(diǎn)中headvex為1的結(jié)點(diǎn)，如上圖圓圈3。

十字鏈表的好處就是因?yàn)榘燕徑颖砗湍驵徑颖碚�合在一起，這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而比較容易求得頂點(diǎn)的出度和入度。

而且除了結(jié)構(gòu)復(fù)雜一點(diǎn)外，其實(shí)創(chuàng)建圖算法的時(shí)間復(fù)雜度是和鄰接表相同的，因此，在有向圖應(yīng)用中，十字鏈表是非常好的數(shù)據(jù)結(jié)構(gòu)模型。

這里就介紹以上三種存儲(chǔ)結(jié)構(gòu)，除了第三種存儲(chǔ)結(jié)構(gòu)外，其他的兩種存儲(chǔ)結(jié)構(gòu)比較簡(jiǎn)單。

二、圖的遍歷

圖的遍歷和樹(shù)的遍歷類(lèi)似，希望從圖中某一頂點(diǎn)出發(fā)訪(fǎng)遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次，這一過(guò)程就叫圖的遍歷。

對(duì)于圖的遍歷來(lái)說(shuō)，如何避免因回路陷入死循環(huán)，就需要科學(xué)地設(shè)計(jì)遍歷方案，通過(guò)有兩種遍歷次序方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

2.1 深度優(yōu)先遍歷

深度優(yōu)先遍歷，也有稱(chēng)為深度優(yōu)先搜索，簡(jiǎn)稱(chēng)DFS。其實(shí)，就像是一棵樹(shù)的前序遍歷。

它從圖中某個(gè)結(jié)點(diǎn)v出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)，然后從v的未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到。若圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中的所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。

我們用鄰接矩陣的方式，則代碼如下所示。