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

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

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

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

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

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

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

對(duì)比圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷算法，會(huì)發(fā)現(xiàn)，它們?cè)跁r(shí)間復(fù)雜度上是一樣的，不同之處僅僅在于對(duì)頂點(diǎn)的訪問(wèn)順序不同�？梢�(jiàn)兩者在全圖遍歷上是沒(méi)有優(yōu)劣之分的，只是不同的情況選擇不同的算法。