算法與數(shù)據(jù)結(jié)構(gòu)無廢話筆記（三）

??算法與數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)學(xué)生的必修課，基礎(chǔ)中的基礎(chǔ)，所以快速上手，找到學(xué)習(xí)方向和感覺十分重要。我在學(xué)習(xí)過程中遇到一本好書，《我的第一本算法書》，把算法講得很淺顯易懂，所以基于這本書的內(nèi)容，提煉出其中的精華，再加上個人的理解，旨在把最干的干貨分享給大家。推薦大家去閱讀原書！

圖的搜索

圖能給我們帶來的便利

想一想圖能給我們帶來的好處吧。假設(shè)圖中有兩個頂點 s 和 t，而我們設(shè)計出了一種算法，可以找到“從 s 到 t 的權(quán)重之和最小”的那條路徑。那么，這種算法就可以應(yīng)用到這些問題上：尋找計算機網(wǎng)絡(luò)中通信時間最短的路徑，尋找路線圖中耗時最短的路徑，尋找路線圖中最省乘車費的路徑等 A。

就像這樣，只要能用圖來表示這些關(guān)系，我們就可以用解決圖問題的算法來解決這些看似不一樣的問題。

圖的搜索指的就是從圖的某一頂點開始，通過邊到達(dá)不同的頂點，最終找到目標(biāo)頂點的過程。根據(jù)搜索的順序不同，圖的搜索算法可分為“廣度優(yōu)先搜索”和“深度優(yōu)先搜索”這兩種。

廣度優(yōu)先搜索

假設(shè)我們一開始位于某個頂點（即起點），此時并不知道圖的整體結(jié)構(gòu)，而我們的目的是從起點開始順著邊搜索，直到到達(dá)指定頂點（即終點）。在此過程中每走到一個頂點，就會判斷一次它是否為終點。廣度優(yōu)先搜索會優(yōu)先從離起點近的頂點開始搜索。

深度優(yōu)先搜索

目的和廣度優(yōu)先搜索一樣都是從起點開始搜索直到到達(dá)指定頂點（終點）。深度優(yōu)先搜索會沿著一條路徑不斷往下搜索直到不能再繼續(xù)為止，然后再折返，開始搜索下一條候補路徑。

就是一根筋，每條路都走到底。

最短路徑算法

貝爾曼-福特算法

貝爾曼 - 福特（Bellman-Ford）算法是一種在圖中求解最短路徑問題的算法。最短路徑問題就是在加權(quán)圖指定了起點和終點的前提下，尋找從起點到終點的路徑中權(quán)重總和最小的那條路徑。

這個算法很暴力！每一輪更新都比較每一條邊！在一次更新中，如果一條邊計算的權(quán)重小于頂點的權(quán)重，則頂點的權(quán)重更新！每次更新需要記錄計算的是從哪個頂點到該頂點的路徑。

重復(fù)對所有邊的更新操作，直到權(quán)重不能被更新為止。

所以每一輪更新都要比較所有的n條邊，理論至多n-1輪更新后找到最小路徑。

一開始一般選從起點開始，假設(shè)其他頂點初始權(quán)重都是無窮大。

第一輪更新：

第二輪：重復(fù)對所有邊的更新操作，直到權(quán)重不能被更新為止。

狄克斯特拉算法

狄克斯特拉（Dijkstra）算法也是求解最短路徑問題的算法。走一步，算一步！一邊逐一確定起點到各個頂點的最短路徑，一邊對圖進(jìn)行搜索。

從離起點近的頂點開始，按順序求出起點到各個頂點的最短路徑整個尋找過程一氣呵成，不用多輪的更新！ 本質(zhì)，不斷選擇頂點！

A* 算法

狄克斯特拉算法會把所有頂點的最短路徑都算出來，但其實一些離終點較遠(yuǎn)的頂點的最短路徑是無用的！ A* 算法會預(yù)先估算一個值（各頂點與終點的距離），并利用這個值來省去一些無用的計算。

上一篇 ！下一篇 ！加油！