電子發(fā)燒友App
深度優(yōu)先搜索算法（Depth-First-Search），是搜索算法的一種。它沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當節(jié)點 v 的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點 v 的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復以上過程，整個進程反復進行直到所有節(jié)點都被訪問為止。DFS 屬于盲目搜索。
深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關(guān)的圖論問題，如最大路徑問題等等。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn) DFS 算法。
深度優(yōu)先遍歷圖算法步驟：
1. 訪問頂點 v；
2. 依次從 v 的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和 v 有路徑相通的頂點都被訪問；
3. 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。
上述描述可能比較抽象，舉個實例：
DFS 在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1；再從 w1 出發(fā)，訪問與 w1 鄰接但還沒有訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。
接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。
算法七：BFS（廣度優(yōu)先搜索）
廣度優(yōu)先搜索算法（Breadth-First-Search），是一種圖形搜索算法。簡單的說，BFS 是從根節(jié)點開始，沿著樹 (圖) 的寬度遍歷樹 (圖) 的節(jié)點。如果所有節(jié)點均被訪問，則算法中止。BFS 同樣屬于盲目搜索。一般用隊列數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn) BFS 算法。
算法步驟：
1. 首先將根節(jié)點放入隊列中。
2. 從隊列中取出第一個節(jié)點，并檢驗它是否為目標。
如果找到目標，則結(jié)束搜尋并回傳結(jié)果。
否則將它所有尚未檢驗過的直接子節(jié)點加入隊列中。
3. 若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結(jié)束搜尋并回傳「找不到目標」。
4. 重復步驟 2。
?
算法八：Dijkstra算法
戴克斯特拉算法（Dijkstra』salgorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹算法使用了廣度優(yōu)先搜索解決非負權(quán)有向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。
該算法的輸入包含了一個有權(quán)重的有向圖 G，以及 G 中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示 G 中所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù) w:E→[0,∞] 定義。因此，w(u,v) 就是從頂點 u 到頂點 v 的非負權(quán)重（weight）。邊的權(quán)重可以想像成兩個頂點之間的距離。任兩點間路徑的權(quán)重，就是該路徑上所有邊的權(quán)重總和。已知有 V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低權(quán)重路徑 (例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對于不含負權(quán)的有向圖，Dijkstra 算法是目前已知的最快的單源最短路徑算法。
算法步驟：
1. 初始時令 S={V0},T={其余頂點}，T 中頂點對應的距離值
若存在，d(V0,Vi) 為弧上的權(quán)值
若不存在，d(V0,Vi) 為∞
2. 從 T 中選取一個其距離值為最小的頂點 W 且不在 S 中，加入 S
3. 對其余 T 中頂點的距離值進行修改：若加進 W 作中間頂點，從 V0 到 Vi 的距離值縮短，則修改此距離值
重復上述步驟 2、3，直到 S 中包含所有頂點，即 W=Vi 為止
工商網(wǎng)監(jiān)
評論