广度优先算法
深度和广度优先算法
- 深度优先算法：使用栈实现，思想是一条路走到底，然后转过头再走另外的路
- 广度优先算法：使用队列实现，思想是先遍历邻居，再遍历邻居的邻居，依次类推...
图是什么？
图由节点和边组成，一个节点可能和众多节点相连，这个相邻的节点称为邻居。
广度优先算法解决的问题
- 从 A 节点触发，有前往 B 节点的路径吗？
- 从 A 节点触发，到 B 节点的最短路径。
查找你的关系网中是否会有芒果商
js 使用广度优先算法进行芒果商的查找
// 通过散列表映射关系网
const hasMango = (): string => {
const network = {
小明: ["小红", "小芳"],
小红: ["小明", "小东"],
小芳: ["小明", "小爱"],
小东: ["小红", "小晓", "小波"],
小爱: ["小芳", "小晓"],
小晓: ["小东", "小爱"],
}
const queue = [] // 需要检查的人
const isChecked = [] // 检查完的人
queue.push("小明")
while (queue.length > 0) {
const people = queue.shift() // 抽一个人出来
if (!isChecked.includes(people)) {
if (people.job === "芒果商") {
return people
} else {
// 如果这个人不是芒果商，把这个人推入检查队列，并把他的狐朋狗友加入queue队列
isChecked.push(people)
queue.concat(network[people])
}
}
}
return ""
}