做AI免费网站,网站托管什么意思,科技公司网站制作公司,南昌百恒信息技术有限公司#x1f4ab;【图论】链式前向星–BFS宽搜遍历
#x1f44f;宽搜背景和实现的功能 输入: n m n:结点数量m:边的数量 输出:到达结点编号为n的最短路径, 每条路长度为1(宽度搜索的前前提条件) #x1f914;思路#xff1a;
采用链式前向星存图数组模拟队列的方法只要队列不…【图论】链式前向星–BFS宽搜遍历
宽搜背景和实现的功能 输入: n m n:结点数量m:边的数量 输出:到达结点编号为n的最短路径, 每条路长度为1(宽度搜索的前前提条件) 思路
采用链式前向星存图数组模拟队列的方法只要队列不为空取出头结点作为待处理的结点 对于每一个待处理的结点优先判断是否已经进行过BFS搜索防止进入有向图死循环到达后继结点的距离为前继结点距离1将该结点所有未处理过的后继节点加入队列中等待处理
⌨️Code
#include iostream
#include cstring
using namespace std;
//宽搜遍历图const int N 10001;
int head[N], next[N], to[N], idx;
int d[N], q[N];
int n, m;inline void add(int u, int v) {to[idx] v, next[idx] head[u], head[u] idx;
}inline int dfs() {int hh 0, tt 0;//定义队头和队尾q[0] 1; // 起点 1memset(d, -1, sizeof d); //d[u] 为 -1 表示没有宽度搜索过该结点 d[1] 0; //d[u] 表示到达结点 u的最小距离 while (hh tt) { //队列不空 int t q[hh ]; //取得对头并出队for (int i head[t]; i ! -1; i next[i]) { //用 i 来遍历该节点所有指向的边 int j to[i]; //j 表示边指向的值if (d[j] -1) { //如果该边指向的结点 j 没有被扩展过 d[j] d[t] 1; //用当前结点的最短路径计算到达该结点的最短路径 q[ tt] j; //该结点入队, 队尾指针后移并赋值 } } }return d[n];
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin n m;// n表示结点数量 m 表示边的数量 memset(head, -1, sizeof head);for (int i 0; i m; i) {int u, v;cin u v;add(u, v);}cout dfs() endl;
}
