BFS广度优先遍历
定义
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
算法解析
访问初始顶点V，访问左右未被访问的邻接点Vi…,递归 Vi
类似于波纹传播。
以广度求最优，求值。
走所有路的出最优的算法。
实例
最优配餐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Vertex implements Cloneable {
public int x;
public int y;
public int step;
public Vertex(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
public Vertex() {
}
}
public static void main(String[] args) {
long[][] map = new long[1001][1001];
Queue<Vertex> q = new LinkedList<Vertex>();
boolean[][] vis = new boolean[1001][1001];
int[][] move = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
Scanner in = new Scanner(System.in);
long size = in.nextLong();
long m = in.nextLong();
long k = in.nextLong();
long d = in.nextLong();
for (int i = 0; i < m; i++) {
int x = in.nextInt();
int y = in.nextInt();
int step = 0;
q.add(new Vertex(x, y, step));
}
for (int i = 0; i < k; i++) {
int x = in.nextInt();
int y = in.nextInt();
int z = in.nextInt();
map[x][y] = z;
}
for (int i = 0; i < d; i++) {
int x = in.nextInt();
int y = in.nextInt();
vis[x][y] = true;
}
in.close();
long cnt = 0;
long ans = 0;
while (!q.isEmpty()) {
Vertex u = q.remove();
for (int i = 0; i < 4; i++) {
Vertex tem = new Vertex();
tem.x = u.x;
tem.y = u.y;
tem.step = u.step;
tem.x += move[i][0];
tem.y += move[i][1];
tem.step++;
if (tem.x > 0 && tem.y <= size && tem.y > 0 && tem.x <= size && !vis[tem.x][tem.y]) {
vis[tem.x][tem.y] = true;
if (map[tem.x][tem.y] != 0) {
ans += map[tem.x][tem.y] * tem.step;
++cnt;
if (cnt == k)
break;
}
q.add(tem);
}
}
}
System.out.println(ans);
}
}
|
wechat
