今天中午的時候呢？我簡單介紹了一下廣度優(yōu)先搜索和深度優(yōu)先搜索蛾号。關(guān)于這兩個概念吧熬尺，如果不知道的時候會感覺很難 但是一旦理解了這個東西 就感覺很簡單褂始。
既然今天談到了BFS，并且好多人都說BFS是很多算法的基礎(chǔ)跪帝，那么我就從基礎(chǔ)開始說起 簡單談一下BFS的應(yīng)用吧今膊。
一、 求BFS兩點(diǎn)之間的路徑
看了標(biāo)題伞剑，可能有點(diǎn)不明白對吧斑唬，先看我們的圖
首先我們根據(jù)上一篇文章的想法來寫一下BFC的代碼吧：
// 圖
let graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E'],
'E':['C','D','F'],
'F':['E']
}
function dfs(graph,startPoint){
let queue = [];
let result = []
queue.push(startPoint);
result.push(startPoint);
while(queue.length>0){
let point = queue.shift();
let nodes = graph[point];
for(let node of nodes){
if(result.includes(node)) continue;
result.push(node);
stack.push(node);
}
}
return result
}
上面就是上一篇文章深入原理講的BFS的代碼，如果有不懂的纸泄，可以返回上一篇文章進(jìn)行專研赖钞，我這里就不多加贅述了。
在一篇文章講到BFS聘裁，我們是從一顆樹引入的雪营。我當(dāng)時講到：在廣度優(yōu)先搜索之下，圖就是沒確定起點(diǎn)的樹衡便。例如我們將起來設(shè)定成A献起，其實(shí)我們也能把樹形結(jié)構(gòu)給畫出來：
如果我們能畫出這個樹的話，其實(shí)就能明白我說得的意思镣陕。如果我們設(shè)定的起點(diǎn)是A谴餐，那么F到A點(diǎn)的路徑就是：F->E->C->A；B點(diǎn)到A的路徑就是B->A
我們來修改一下前面的代碼吧：
// 別問我為什么修改了一下上面的代碼呆抑。其實(shí)一個意思
// 其實(shí)我在為明天中午的復(fù)習(xí)set做準(zhǔn)備岂嗓，順便復(fù)習(xí)了一下api 哈哈
function bfs(graph,startPoint){
let queue = [];
let result = new Set();
let tree = {};
queue.push(startPoint);
result.add(startPoint);
tree[startPoint] = ""
while(queue.length > 0){
let point = queue.shift();
let nodes = graph[point];
for(let node of nodes){
if(result.has(node)) continue;
result.add(node)
queue.push(node)
tree[node] = point;
}
}
return tree
}
function shortDistance(tree,point){
let node = point
let distance = [point]
while(tree[node]!=""){
node = tree[node];
distance.push(node);
}
return distance;
}
怎么理解上面的代碼呢？
很簡單鹊碍，就是將每個數(shù)據(jù)在出棧的時候記錄一下他的父節(jié)點(diǎn)是誰厌殉？如下圖所示：
如上圖所示，第一段代碼就相當(dāng)于給每一個元素建立了一個戶口薄侈咕，每個人的身份信息全部都填寫到了本本上面公罕，如果想找找到路徑，就直接從當(dāng)前節(jié)點(diǎn)開始盤問耀销。例如：E到A的路徑楼眷，就可以如下操作：
就能找出E->C->A的路徑。
二、 求BFS的最短路徑/距離
上面用一個例子簡單的介紹了一個廣度深度優(yōu)先算法的兩個點(diǎn)的路徑罐柳，但是其實(shí)很容易就會發(fā)現(xiàn)得到的答案并不是唯一的掌腰，比如就上面的條件來說，我也可以畫成這樣的樹 也能滿足需求：
如上所示张吉，其實(shí)這樣也是能滿足需求的辅斟，針對這種比較不唯一的情況 我就大膽了再給其加上限定條件。如下圖所示：
如上圖所示芦拿，A到C的路徑 一共有A->C和A->B->C。但是A->C的距離是5查邢，A->B->C的距離是3蔗崎。所以此時的最短路徑應(yīng)該是A->B->C。
具體的排序方式 同樣我們用下面的一組套圖來解釋一下扰藕。
同樣我們先把A放進(jìn)容器中缓苛。
將A移出容器，并將與A相連的B邓深，C 移入容器內(nèi)未桥，再比較與B，C相連的距離誰比較近芥备。明顯B距離A比較近冬耿。
將B移出容易，并且將與B相連的C,D加入容器內(nèi)萌壳，此時我們發(fā)現(xiàn)容器內(nèi)有兩個C亦镶，而后者的C比前者要小。
將距離比較小的C和距離比較大的C調(diào)換位置袱瓮，然后移出缤骨，并且將與C相連的D,E加入容易內(nèi)。
同理將容器內(nèi)比較小的D移出容器尺借，當(dāng)我們再次將容器內(nèi)比較小的C和D移出時绊起，發(fā)現(xiàn)之前移出的數(shù)據(jù)里面中已經(jīng)存在C，D燎斩。此時就將C虱歪，D給舍棄
最后就這樣得到了所謂的最短路徑了。來我們用代碼來演示一下：
function bfs(graph,startPoint){
let queue = [];
let result = {};
let seen = new Set();
let distance = initDistance(graph,startPoint);
queue.push({distance:0,name:startPoint});
result[startPoint] ={parent:"",distance:0,};
while(queue.length > 0){
let point = queue.shift();
let dist = point.distance;
let vertex = point.name;
seen.add(vertex);
let nodes = graph[vertex]
for(let node in nodes){
if(!seen.has(node)&&dist+nodes[node]<distance[node]) {
result[node]= {parent:vertex,distance:dist+nodes[node]};
distance[node] = dist+nodes[node];
queue.push({distance:dist+nodes[node],name:node});
}
}
queue.sort((a,b)=>{
return a.distance-b.distance;
})
}
console.log(result)
return result;
}
那么此時我們的數(shù)據(jù)結(jié)構(gòu)就應(yīng)該是這個樣子了哦：
let graph = {
'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}
}
說在最后
關(guān)于BFS用法呢瘫里？其實(shí)還是比較簡單的实蔽。也是只要想通了，寫出來還是比較簡單的谨读。我這里呢局装？就簡單的寫一兩個例子來給諸位當(dāng)一個敲門磚吧。如果之前有研究過第二個問題，其實(shí)很容易就發(fā)現(xiàn)其實(shí)第二個問題就是大名鼎鼎的Dijkstra算法铐尚。如果對圖有深層次的興趣拨脉，也可以深入了解一下哦 畢竟知道總比不知道好。
好了宣增，好了 中午睡覺的時間真的又被我活生生的寫完了玫膀，看來今天又沒午覺睡了。還是去躺躺一下吧爹脾。
