重點(diǎn)需要解釋虛線箭頭的含義。它其實(shí)就是此圖的逆鄰接表的表示。對于v0來說，它有兩個頂點(diǎn)v1和v2的入邊。因此的firstin指向頂點(diǎn)v1的邊表結(jié)點(diǎn)中headvex為0的結(jié)點(diǎn)，如上圖圓圈1。接著由入邊結(jié)點(diǎn)的headlink指向下一個入邊頂點(diǎn)v2，如上圖圓圈2。對于頂點(diǎn)v1，它有一個入邊頂點(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)建圖算法的時間復(fù)雜度是和鄰接表相同的，因此，在有向圖應(yīng)用中，十字鏈表是非常好的數(shù)據(jù)結(jié)構(gòu)模型。

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

二、圖的遍歷

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

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

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

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

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

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