從頭開始複習算法之我們來簡單的應用一下BFS | 程式前沿

既然今天談到了BFS，並且好多人都說BFS是很多算法的基礎，那麼我就從基礎開始說起簡單談一下BFS的應用吧。

目錄. 1. 一、 求BFS兩點之間的路徑; 2. 程式語言前端開發IOS開發Android開發雲端運算人工智慧伺服器搜尋資料庫軟體開發工具從頭開始複習算法之我們來簡單的應用一下BFS2019.10.29程式語言HOME程式語言從頭開始複習算法之我們來簡單的應用一下BFSAdvertisement今天中午的時候呢？我簡單介紹了一下廣度優先搜索和深度優先搜索。

關於這兩個概念吧，如果不知道的時候會感覺很難但是一旦理解了這個東西就感覺很簡單。

既然今天談到了BFS，並且好多人都說BFS是很多算法的基礎，那麼我就從基礎開始說起簡單談一下BFS的應用吧。

目錄1.一、求BFS兩點之間的路徑2.二、求BFS的最短路徑/距離3.說在最後4.相關文章一、求BFS兩點之間的路徑看了標題，可能有點不明白對吧，先看我們的圖首先我們根據上一篇文章的想法來寫一下BFC的代碼吧：//圖 letgraph={ 'A':['B','C'], 'B':['A','C','D'], 'C':['A','B','D','E'], 'D':['B','C','E'], 'E':['C','D','F'], 'F':['E'] } functiondfs(graph,startPoint){ letqueue=[]; letresult=[] queue.push(startPoint); result.push(startPoint); while(queue.length>0){ letpoint=queue.shift(); letnodes=graph[point]; for(letnodeofnodes){ if(result.includes(node))continue; result.push(node); stack.push(node); } } returnresult } 上面就是上一篇文章深入原理講的BFS的代碼，如果有不懂的，可以返回上一篇文章進行專研，我這裡就不多加贅述了。

在一篇文章講到BFS，我們是從一顆樹引入的。

我當時講到：在廣度優先搜索之下，圖就是沒確定起點的樹。

例如我們將起來設定成A，其實我們也能把樹形結構給畫出來：如果我們能畫出這個樹的話，其實就能明白我說得的意思。

如果我們設定的起點是A，那麼F到A點的路徑就是：F->E->C->A；B點到A的路徑就是B->A我們來修改一下前面的代碼吧：//別問我為什麼修改了一下上面的代碼。

其實一個意思 //其實我在為明天中午的複習set做準備，順便複習了一下api哈哈 functionbfs(graph,startPoint){ letqueue=[]; letresult=newSet(); lettree={}; queue.push(startPoint); result.add(startPoint); tree[startPoint]="" while(queue.length>0){ letpoint=queue.shift(); letnodes=graph[point]; for(letnodeofnodes){ if(result.has(node))continue; result.add(node) queue.push(node) tree[node]=point; } } returntree } functionshortDistance(tree,point){ letnode=point letdistance=[point] while(tree[node]!=""){ node=tree[node]; distance.push(node); } returndistance; } 怎麼理解上面的代碼呢？很簡單，就是將每個數據在出棧的時候記錄一下他的父節點是誰？如下圖所示：如上圖所示，第一段代碼就相當於給每一個元素建立了一個戶口薄，每個人的身份信息全部都填寫到了本本上面，如果想找找到路徑，就直接從當前節點開始盤問。

例如：E到A的路徑，就可以如下操作：就能找出E->C->A的路徑。

二、求BFS的最短路徑/距離上面用一個例子簡單的介紹了一個廣度深度優先算法的兩個點的路徑，但是其實很容易就會發現得到的答案並不是唯一的，比如就上面的條件來說，我也可以畫成這樣的樹也能滿足需求：如上所示，其實這樣也是能滿足需求的，針對這種比較不唯一的情況我就大膽了再給其加上限定條件。

如下圖所示：如上圖所示，A到C的路徑一共有A->C和A->B->C。

但是A->C的距離是5，A->B->C的距離是3。

所以此時的最短路徑應該是A->B->C。

具體的排序方式同樣我們用下面的一組套圖來解釋一下。

同樣我們先把A放進容器中。

將A移出容器，並將與A相連的B，C移入容器內，再比較與B，C相連的距離誰比較近。

明顯B距離A比較近。

將B移出容易，並且將與B相連的C,D加入容器內，此時我們發現容器內有兩個C，而後者的C比前者要小。

將距離比較小的C和距離比較大的C調換位置，然後移出，並且將與C相連的D,E加入容易內。

同理將容器內比較小的D移出容器，當我們再次將容器內比較小的C和D移出時，發現之前移出的數據裡面中已經存在C，D。

此時就將C，D給捨棄最後就這樣得到了所謂的最短路徑了。

來我們用代碼來演示一下：functionbfs(graph,startPoint){ letqueue=[]; letresult={}; letseen=newSet(); letdistance= initDistance(graph,startPoint); queue.push({distance:0,name:startPoint}); result[startPoint]={parent:"",distance:0,}; while(queue.length>0){ letpoint=queue.shift(); letdist=point.distance; letvertex=point.name; seen.add(vertex); letnodes=graph[vertex] for(letnodeinnodes){ if(!seen.has(node)&&dist+nodes[node]{ returna.distance-b.distance; }) } console.log(result) returnresult; } 那麼此時我們的數據結構就應該是這個樣子了哦：letgraph={ 'A':{'B':1,'C':5}, 'B':{'A':1,'C':2,'D':3}, 'C':{'A':5,'B':2,'D':4,'E':10}, 'D':{'B':3,'C':4,'E':3}, 'E':{'D':3,'C':10,'F':5}, 'F':{'E':5} } 說在最後關於BFS用法呢？其實還是比較簡單的。

也是隻要想通了，寫出來還是比較簡單的。

我這裡呢？就簡單的寫一兩個例子來給諸位當一個敲門磚吧。

如果之前有研究過第二個問題，其實很容易就發現其實第二個問題就是大名鼎鼎的Dijkstra算法。

如果對圖有深層次的興趣，也可以深入瞭解一下哦畢竟知道總比不知道好。

好了，好了中午睡覺的時間真的又被我活生生的寫完了，看來今天又沒午覺睡了。

還是去躺躺一下吧。

相關文章讓你從頭到尾把promise整的明明白白從頭開始複習js之這可能是最全的字符串用法從頭開始複習js之讓你徹徹底底搞清楚數組從頭開始複習算法之徹徹底底搞清楚堆排序AdvertisementAdvertisement近期文章學習OpenGLES之激光特效2020.08.18學習OpenGLES之透明和混合2020.08.18學習OpenGLES之基本紋理2020.08.18學習OpenGLES之基本光照2020.08.18學習OpenGLES之繪製一個正方體2020.08.18學習OpenGLES之攝像機2020.08.18學習OpenGLES之透視和正交投影2020.08.18學習OpenGLES之變換矩陣2020.08.18學習OpenGLES之繪製更多的圖形2020.08.18學習OpenGLES之什麼是Shader？2020.08.18AdvertisementAdvertisement