深度優(yōu)先遍歷（DFS）Depth First search
深度優(yōu)先遍歷例題
連通圖的深度優(yōu)先遍歷類似與樹的先根遍歷
算法實(shí)現(xiàn)
鄰接矩陣實(shí)現(xiàn)無向圖的深度優(yōu)先遍歷
輔助數(shù)組
DFS結(jié)果是213546
使用鄰接矩陣實(shí)現(xiàn)深度優(yōu)先遍歷
效率分析
■用鄰接矩陣來表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行
行洒琢，時(shí)間復(fù)雜度為O(n7)拼余。
■用鄰接表來表示圖，雖然有2e個(gè)表結(jié)點(diǎn)空盼，但只需掃描e個(gè)結(jié)點(diǎn)即可
完成遍歷书幕，加上訪問n個(gè)頭結(jié)點(diǎn)的時(shí)間，時(shí)間復(fù)雜度為O(n+ e)揽趾。
結(jié)論:
稠密圖適于在鄰接矩陣.上進(jìn)行深度遍歷;
稀疏圖適于在鄰接表上進(jìn)行深度遍歷台汇。
廣度優(yōu)先遍歷（BFS）Breadth First Search
廣度優(yōu)先遍歷例題
廣度優(yōu)先遍歷非遞歸遍歷
BFS算法效率分析
●如果使用鄰接矩陣，則BFS對(duì)于每個(gè)被訪問到的頂點(diǎn)但骨， 都要循鞏
檢測(cè)矩陣中的整整一行( n個(gè)元素) ,總的時(shí)間代價(jià)為O(n7)励七。
●用鄰接表來表示圖，雖然有2e個(gè)表結(jié)點(diǎn)奔缠，但只需掃描e個(gè)結(jié)點(diǎn)即
可完成遍歷掠抬，加上訪問n個(gè)頭結(jié)點(diǎn)的時(shí)間，時(shí)間復(fù)雜度為O(n+e)校哎。
DSF和BSF比較
●空間復(fù)雜度相同两波，都是O(n)(借用了堆椡剑或隊(duì)列) ;
●時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)(鄰接矩陣或鄰接表)有關(guān)，而與搜索路徑無
關(guān)腰奋。
