图的邻接矩阵 BFS 搜索模板

#include <bits/stdc++.h>
using namespace std;

const int N = 105;           // 根据题目点的数量范围调整
int g[N][N];                 // 邻接矩阵，g[u][v] = 1 表示有边
bool vis[N];
int step[N];
int n, m, st, ed;            // 点数、边数、起点、终点

void bfs() {
	vis[st] = 1;
	queue<int> q;
	q.push(st);
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v = 1; v <= n; v++) {      // 遍历所有点
			if (g[u][v] == 0 || vis[v]) continue;  // 无边或已访问
			step[v] = step[u] + 1;
			vis[v] = 1;
			if (v == ed) return;
			q.push(v);
		}
	}
}

int main() {
	cin >> n >> m >> st >> ed;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
        g[u][v] = 1;      // 无权图
		// 无向图需要反向边
		// g[v][u] = 1;
	}
	
	bfs();
	if (!vis[ed]) cout << -1 << endl;
	else cout << step[ed] << endl;
	return 0;
}