Catalog
图的广度优先遍历

#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 9999999;
struct node {
int x, s;
};
struct node que[2501];
int e[101][101], book[51];
int main() {
int head, tail;
int n, m, a,b, cur, start, end, flag = 0;
cin >> n >> m >> start >> end;
for(int i = 1; i<=n;i++)
for (int j = 1; j <= n; j++)
{
if (i == j) e[i][j] = 0;
else e[i][j] = maxn;
}
for (int i = 1; i <= m; i++) {
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1;//无向图
}
head = 1;
tail = 1;
que[head].x = start;
que[head].s = 0;
tail++;
book[start] = 1;
while (head < tail) {
cur = que[head].x;
for (int j = 1; j <= n; j++) {
if (e[cur][j] != maxn && book[j] == 0) {
que[tail].x = j;
que[tail].s = que[head].s + 1;
tail++;
book[j] = 1;
}
if (que[tail - 1].s == end) {
flag = 1;
break;
}
}
if (flag == 1)
break;
head++;
}
printf("%d", que[tail - 1].s);
return 0;
}

​ 本题也可使用深度优先搜索,但是这里使用广度优先搜索会更快。广度优先搜索会更加适用于所有边的 权值相同的情况。

Author: superzhaoyang
Link: http://yoursite.com/2019/09/25/图的广度优先遍历/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment