广度优先搜索(BFS) 模板

科幻大脑 · 2020-10-31 19:14:07 · 个人记录

广度优先搜索 (BFS)

目的：找出两点间最短距离、最少修改次数等

使用：由0点出发遍历周围较广的区域

时间复杂度：对于给定图 G=(V,E) 有O(V+E)

推荐题目： P1443 P1135 P1032 P1379

void f(int a){
    //你的下一个点的计算 
}

void BFS(){
    queue<int> q;//队列模拟图的搜索 
    q.push(A);// A为0点数据
    while(!q.empty()){
        int a = q.front(), b; 
        q.pop();//取队首并出队
        b = f(a);
        if(/* 你的数据满足的条件 */){
            q.push(b);//新数据入队 
        }
    } 
    //搜索完毕 
}