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

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在一起，這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而比較容易求得頂點的出度和入度。

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

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

二、圖的遍歷

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

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

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

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

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

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