算法图解第6章——广度优先搜索

队列是一种先进先出的数据结构；栈是一种先进后出的数据结构；

散列表是无序的，因此添加健-值对的顺序无关紧要；

1、利用图来建立模型，再使用广度优先搜索来解决问题；

2、需要按加入顺序来检查搜索列表中的人，所以需要使用队列来找出最短路径；

3、检查过的人不能再查，否则会进入死循环。

/* 广度优先搜索 */
/* 散列表存储数据 */
var graph = {}
graph["you"] = ["Alice", "Bob", "Colin", "Sam"]
graph["Alice"] = ["Daniel", "Ellen"]
graph["Bob"] = ["Flank", "Ellen"]
graph["Colin"] = []
graph["Sam"] = []
graph["Daniel"] = []
graph["Flank"] = []
graph["Ellen"] = []
/* 数组存储队列 */
function search(name) {
  var search_quene = []
  search_quene = search_quene.concat(graph[name])
  searched = []
  while (search_quene.length > 0) {
    console.log('search_quene', search_quene);
    console.log('searched', searched);
    person = search_quene.shift()
    if (searched.indexOf(person) === -1) {
      if (personIsSeller(person)) {
        console.log(person + ' is mongo seller!');
        return true;
      } else {
        console.log(person + ' is not a seller!');
        search_quene = search_quene.concat(graph[person])
        searched.push(person)
      }
    }
  }
  return false
}
/* 已经判断过的不再进入队列 */
function personIsSeller(name) {
  return (/m$/gi).test(name)
}

search("you")