今天中午的时候呢？我简单介绍了一下广度优先搜索和深度优先搜索。关于这两个概念吧，如果不知道的时候会感觉很难 但是一旦理解了这个东西 就感觉很简单。
既然今天谈到了BFS，并且好多人都说BFS是很多算法的基础，那么我就从基础开始说起 简单谈一下BFS的应用吧。
一、 求BFS两点之间的路径
看了标题，可能有点不明白对吧，先看我们的图
首先我们根据上一篇文章的想法来写一下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的代码，如果有不懂的，可以返回上一篇文章进行专研，我这里就不多加赘述了。
在一篇文章讲到BFS，我们是从一颗树引入的。我当时讲到：在广度优先搜索之下，图就是没确定起点的树。例如我们将起来设定成A，其实我们也能把树形结构给画出来：
如果我们能画出这个树的话，其实就能明白我说得的意思。如果我们设定的起点是A，那么F到A点的路径就是：F->E->C->A；B点到A的路径就是B->A
我们来修改一下前面的代码吧：
// 别问我为什么修改了一下上面的代码。其实一个意思
// 其实我在为明天中午的复习set做准备，顺便复习了一下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;
}
怎么理解上面的代码呢？
很简单，就是将每个数据在出栈的时候记录一下他的父节点是谁？如下图所示：
如上图所示，第一段代码就相当于给每一个元素建立了一个户口薄，每个人的身份信息全部都填写到了本本上面，如果想找找到路径，就直接从当前节点开始盘问。例如：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给舍弃
最后就这样得到了所谓的最短路径了。来我们用代码来演示一下：
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;
}
那么此时我们的数据结构就应该是这个样子了哦：
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}
}
说在最后
关于BFS用法呢？其实还是比较简单的。也是只要想通了，写出来还是比较简单的。我这里呢？就简单的写一两个例子来给诸位当一个敲门砖吧。如果之前有研究过第二个问题，其实很容易就发现其实第二个问题就是大名鼎鼎的Dijkstra算法。如果对图有深层次的兴趣，也可以深入了解一下哦 毕竟知道总比不知道好。
好了，好了 中午睡觉的时间真的又被我活生生的写完了，看来今天又没午觉睡了。还是去躺躺一下吧。
