本文主要是介绍基础算法学习---树的bfs,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
模板
//起始位置为u,求v点最短路
//点之间距离为1
int bfs(int u,int v){
int tt = 0,hh = 0;
memset(d,-1,sizeof d);
d[u] = 0;
q[0] = u;
while(hh <= tt){
//取出点
int t = q[hh ++];
//遍历一步能走到的点
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
if(d[j] == -1){
d[j] = d[t] + 1;
q[++ tt] = j;
}
}
}
//返回结果
return d[v];
}
图中点的层次
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int e[N],ne[N],h[N],idx;
int d[N],q[N];
int n,m;
//建立树图
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int bfs(){
int tt = 0,hh = 0;
//初始化距离为0,初始位置入队
memset(d,-1,sizeof d);
d[1] = 0;
q[0] = 1;
//走过每一个点
while(hh <= tt){
int t = q[++ hh];
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
if(d[j] == -1){
d[j] = d[t] + 1;
q[++ tt] = j;
}
}
}
//返回需要点的值
return d[n];
}
int main(){
cin >> n >> m;
while(m --){
int a,b;
cin >> a >> b;
add(a,b);
}
cout << bfs();
}
这篇关于基础算法学习---树的bfs的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!