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

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

圖的搜索

圖能給我們帶來(lái)的便利

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

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

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

廣度優(yōu)先搜索

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

深度優(yōu)先搜索

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

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

最短路徑算法

貝爾曼-福特算法

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

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

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

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

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

第一輪更新：

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

狄克斯特拉算法

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

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

A* 算法

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

上一篇 ！下一篇 ！加油！