如果使用的是鄰接表存儲結(jié)構(gòu)，其DFSTraverse函數(shù)的代碼幾乎是相同的，只是在遞歸函數(shù)中因為將數(shù)組換成了鏈表而有不同，代碼如下。

對比兩個不同的存儲結(jié)構(gòu)的深度優(yōu)先遍歷算法，對于n個頂點e條邊的圖來說，鄰接矩陣由于是二維數(shù)組，要查找某個頂點的鄰接點需要訪問矩陣中的所有元素，因為需要O(n2)的時間。而鄰接表做存儲結(jié)構(gòu)時，找鄰接點所需的時間取決于頂點和邊的數(shù)量，所以是O(n+e)。顯然對于點多邊少的稀疏圖來說，鄰接表結(jié)構(gòu)使得算法在時間效率上大大提高。

2.2 廣度優(yōu)先遍歷

廣度優(yōu)先遍歷，又稱為廣度優(yōu)先搜索，簡稱BFS。圖的廣度優(yōu)先遍歷就類似于樹的層序遍歷了。

鄰接矩陣做存儲結(jié)構(gòu)時，廣度優(yōu)先搜索的代碼如下。

對于鄰接表的廣度優(yōu)先遍歷，代碼與鄰接矩陣差異不大， 代碼如下。

對比圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷算法，會發(fā)現(xiàn)，它們在時間復(fù)雜度上是一樣的，不同之處僅僅在于對頂點的訪問順序不同。可見兩者在全圖遍歷上是沒有優(yōu)劣之分的，只是不同的情況選擇不同的算法。