面试算法： 广度优先搜索 BFS

广度优先搜索 BFS

• 广度优先搜索让你能够找出两样东西之间的最短距离，不适合加权图。
• 找出A点到B点的最短距离。

// 用字典表示图形关系，遍历寻找 // 从自己出发，寻找邻居，如果找到直接返回，没找到将邻居入栈，继续寻找，直到所有节点搜索完毕。 let graph = {} graph['you'] = ['alice', 'bob', 'ceed'] graph['bob'] = ['anuj', 'peggy','you'] graph['alice'] = ['peggy'] graph['ceed'] = ['thom', 'jonny'] graph['anuj'] = [] graph['peggy'] = [] graph['thom'] = [] graph['jonny'] = [] console.log(graph) let searchHistory = [] // 搜索标记 let search = [].concat(graph['you']) // 搜索队列 while (search.length) { let person = search.shift() // 如果没检查过继续检查 if (searchHistory[person] === undefined){ if (isSeller(person)) { // 找到了 console.log('find', person) break; } else { // 未找到，将邻居加入搜索队列 search = search.concat(graph[person]) // 标记已检查 searchHistory.push(person) } } } // 选后缀m作为目标 function isSeller(person) { return person.lastIndexOf('m') !== -1 }