跳到主要内容

宽度优先搜索（BFS）算法之一——基础

1.1 宽度优先搜索（BFS）定义​

Breadth-First Search 宽度优先搜索算法（Breadth-First Search）（也称为广度优先搜索）主要运用于树、图和矩阵（这三种可以都归类在图中），用于在图中从起始顶点开始逐层地向外探索，直到找到目标顶点为止。

本课主要讨论对树进行搜索。

树的宽度优先搜索 即 树的层序遍历 ：逐层访问树的节点，并按照层级顺序输出节点的值。从树的根节点开始，逐层向下遍历，先访问当前层的所有节点，然后再访问下一层的节点，依次类推直到遍历完整棵树。

1.2 宽度优先搜索思路​

宽度优先搜索BFS示意图一

宽度优先搜索BFS示意图二

宽度优先搜索BFS与DFS的区别示意图

1.3 宽度优先搜索算法实现​

根据上面的思路可以用一个队列来辅助实现BFS.

宽度优先搜索BFS队列示意图一

宽度优先搜索BFS队列示意图二

1.3、基本模板框架​

我们可以总结一个基本的DFS算法框架如下：

//宽度搜索
void bfs(State a){
    队头指针 head=1,队尾指针 tail=1;
    起始状态a入队
    while(head<=tail){
        取出队首元素 State=que[head];
        队头指针后移 head++;
        尝试从队首元素出发可以得到的n个状态
        for(int i=1;i<=n;i++){
            if(满足条件){
                队尾后移，tail++
                状态入队，并标记
            }
            if(到达终点) {
                退出for和while循环。
            }
        }
    }
}


//另一种
int BFS(Node start, Node target) {
    入队(初始状态);
    visited[初始状态] = true;
    while(!空队) {
        for() { // 状态转换
            Node node = 队首元素;
            对node的处理，生成新node状态;
            if (visited[node] == true)
                continue;
            if (node == target) {
                输出答案;
                return 0;
            }
            v[node] = true;
            入队(node);
        }
    出队();
    }
    
}

*学习笔记​

暂没有学习笔记，快来抢first blood ！