Skip to main content

广度优先搜索

图​

广度优先搜索是一种图算法，图由节点和边组成。

graph

广度优先搜索​

广度优先搜索是一种用于图的查找算法，可以帮助回答两类问题:

  • 从节点A出发，有前往节点B的路径吗？
  • 从节点A出发，前往节点B的哪条路径最短？

图中关系的远近​

level

在广度优先查找中，一度关系胜过二度关系，二度关系胜过三度关系...以此类推。因此应该先在一度关系中搜索，确定其中没有要查找的目标（比如芒果销售商）后， 才在二度关系中查找。

实现​

1、我们要创建一个查找队列（对，队列先进入的先查询，后进入的后查询） 2、首先将一度关系放入查找队列中 3、从队列中依次出队检查其是否是我们要查找的目标，如果是结束，如果不是将其直接邻居加入队尾 4、为了避免有循环的情况，还应该维护一个已检查人员的散列表，检查过的对象加入散列表，只有未检查过的对象才检查

BFS

代码实现​

// 数据源 (描述的是图的结构)
let sourceObj = {
    'me': ['小明', '小红', '小亮'],
    '小明': ['a', 'b', 'c'],
    'b': ['d', 'e'],
    'c': ['苹果', '香蕉', '栗子']
}
// 广度优先搜索
function bfsSearch(target, name) {
    let judgeQueue = []; // 检查队列
    let judgedArr = []; // 已检查
    judgeQueue.push(...sourceObj[name]);
    while (judgeQueue.length) {
        let curr = judgeQueue.shift(); // 取出队列队首元素
        if (!judgedArr.includes(curr)) { // 判断元素是否已经检查过了
            if (curr === '苹果') { // 执行查找判断的逻辑
                console.log('找到了！！');
                return true;
            } else {
                judgeQueue.push(...sourceObj[curr]); // 判断为否，则将其邻居加入队尾
                judgedArr.push(curr); // 将元素标记为已检查
            }
        }
    }
    return false; // 直到队列为空还没找到则说明图中没有目标元素，返回false
}