【图论】链式前向星实现图的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;					// 起点 1
	memset(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;
}