【图论】链式前向星实现图的BFS搜索

本文主要是介绍【图论】链式前向星实现图的BFS搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

💫【图论】链式前向星–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;
}

这篇关于【图论】链式前向星实现图的BFS搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---