2018年國家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(15)
如果使用的是鄰接表存儲(chǔ)結(jié)構(gòu),其DFSTraverse函數(shù)的代碼幾乎是相同的,只是在遞歸函數(shù)中因?yàn)閷?shù)組換成了鏈表而有不同,代碼如下。
對比兩個(gè)不同的存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先遍歷算法,對于n個(gè)頂點(diǎn)e條邊的圖來說,鄰接矩陣由于是二維數(shù)組,要查找某個(gè)頂點(diǎn)的鄰接點(diǎn)需要訪問矩陣中的所有元素,因?yàn)樾枰狾(n2)的時(shí)間。而鄰接表做存儲(chǔ)結(jié)構(gòu)時(shí),找鄰接點(diǎn)所需的時(shí)間取決于頂點(diǎn)和邊的數(shù)量,所以是O(n+e)。顯然對于點(diǎn)多邊少的稀疏圖來說,鄰接表結(jié)構(gòu)使得算法在時(shí)間效率上大大提高。
2.2 廣度優(yōu)先遍歷
廣度優(yōu)先遍歷,又稱為廣度優(yōu)先搜索,簡稱BFS。圖的廣度優(yōu)先遍歷就類似于樹的層序遍歷了。
鄰接矩陣做存儲(chǔ)結(jié)構(gòu)時(shí),廣度優(yōu)先搜索的代碼如下。
對于鄰接表的廣度優(yōu)先遍歷,代碼與鄰接矩陣差異不大, 代碼如下。
對比圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷算法,會(huì)發(fā)現(xiàn),它們在時(shí)間復(fù)雜度上是一樣的,不同之處僅僅在于對頂點(diǎn)的訪問順序不同。可見兩者在全圖遍歷上是沒有優(yōu)劣之分的,只是不同的情況選擇不同的算法。
(編輯:姜芃)
- 2020年全國事業(yè)單位招考信息匯總(4月27日)04-27
- 2020年四川省宜賓學(xué)院招聘高層次人才267人公告04-27
- 2020年江蘇省蘇州張家港市衛(wèi)生健康系統(tǒng)事業(yè)單位招聘292人簡章04-27
- 2020年浙江省紹興上虞區(qū)衛(wèi)健系統(tǒng)招聘高層次及緊缺專業(yè)畢業(yè)生91人公告04-27
- 2020年浙江省溫州平陽縣事業(yè)單位引進(jìn)人才109人公告04-27
- 2020年廣東省韶關(guān)仁化縣第二批丹霞英才暨急需緊缺人才網(wǎng)絡(luò)視頻招聘117人公告04-27