欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

和小哥哥一起刷洛谷(4) 图论之广度优先搜索BFS

程序员文章站 2022-04-30 09:09:10
...

关于bfs:

你怎么会连这个都不知道!!!自己好好谷歌一下!!!(其实我也刚学)

bfs伪代码:

while(队列非空){
    取出队首元素u;
    弹出队首元素;
    u染色为黑色;
    for(int i=0;i<u的出度){
        if(i非白色) continue;
        u的第i个出线连着的点入队;
        i染为灰色;
    }
}

可爱的分割线


无权最短路

显然,你在洛谷上是搜不到这题的,因为这是我们学校团队的题。所以还是找个小板凳专心听我讲吧。

题目描述:

给定无权无向图G(V,E)和源点s/终点t,求 s->t 的最短路径。

假设读入边的列表是有(字典)序的(既邻接表就是有序的)。

输入输出格式:

输入格式:

第一行包含4个整数N、M、s、t,表示该图共有N个结点和M条无向边。(N <= 5000,M <= 200000)。起点为s,终点为t。

接下来M行,每行包含2个整数{u,v},表示有一条无向边连接结点u、v

输出格式:

输出最短路的长度(边数)

若无法到达,输出"No path"

样例:

输入:

4 3 1 4
1 2
1 3
2 4

输出:

2

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
const int NR=5005;
using namespace std;
struct Edge{
    //一个存储权值的结构体,为bfs模板,此题无用
    int v,w;
    Edge(int v,int w):v(v),w(w){}
};
vector<Edge> save[5005];//邻接表
int d[NR];//记录距离的数组
int main()
{
    int n,m,s,t;
    cin>>n>>m>>s>>t;//输入
    char color[n+1];//判断是否去过(没去过:"w",正在考虑(在队列中):"g",已经完全考虑:"b")
    memset(color,'w',sizeof(color));//染色数组重置为白色
    
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;//输入每条线的起点和终点
        save[a].push_back(Edge(b,1));//因为是无向图,所以在起点连接的点中增加终点
        save[b].push_back(Edge(a,1));//还要在终点连接的点中增加起点
    }
    
    d[s]=0;//起点距离起点的距离设为零
    queue<int> q;//bfs处理队列
    q.push(s);//起点入队
    color[s]='g';//起点染色成灰色
    while(!q.empty()){
        int u=q.front();//取出队首的一项
        q.pop();//弹出
        color[u]='b';//标记为黑色
        for(int i=0;i<save[u].size();i++){//拓展出所有子节点
            if(color[save[u][i].v]!='w') continue;
            if(save[u][i].v==t){
                cout<<d[u]+1;//如果这个位置是终点,则输出
                return 0;
            }
            d[save[u][i].v]=d[u]+1;//计算距离
            color[save[u][i].v]='g';//染灰色
            q.push(save[u][i].v);//进队
        }
    }
    cout<<"No path";
    return 0;
}

转载于:https://www.cnblogs.com/BlogE/p/luogu_day4.html