BFS广度优先遍历

定义

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

算法解析

访问初始顶点V，访问左右未被访问的邻接点Vi…,递归 Vi

类似于波纹传播。

以广度求最优，求值。

走所有路的出最优的算法。

实例

​ 最优配餐

QQ截图20210527113840.png

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);

    }

}