算法核心-广度优先遍历算法

分析&回答

广度优先遍历与深度优先遍历类似，也是查询的方法之一，他也是从某个状态出发查询可以到达的所有状态。

但不同与深度优先遍历，广度优先遍历总是先去查询距离初始状态最近的状态。

广度优先遍历算法解决问题 （引爆最多的炸弹）

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

class Solution {
    public int maximumDetonation(int[][] bombs) {
        // 构建有向图，i j 为不同炸弹
        List<List<Integer>> graph = IntStream.range(0, bombs.length).mapToObj(i -> new ArrayList<Integer>()).collect(Collectors.toList());
        for(int i = 0; i < bombs.length; i++) {
            for(int j = 0; j < bombs.length; j++) {
                if(i != j && isDetonates(i, j, bombs)) {
                    graph.get(i).add(j);
                }
            }
        }

        int ans = 0;
        // 遍历每一个炸弹，更新能引爆的最大数量
        for(int i = 0; i < bombs.length; i++) {
            ans = Math.max(dfs(i, graph, new boolean[bombs.length]), ans);
        }

        return ans;
    }

    private int dfs(int u, List<List<Integer>> graph, boolean[] visited) {
        visited[u] = true;
        // 当流中没有满足过滤条件的元素的时候终止
        return 1 + graph.get(u).stream().filter(v -> !visited[v]).mapToInt(v -> dfs(v, graph, visited)).sum();
    }

    // isDetonates：判断 炸弹i 能否相互引爆 炸弹j
    private boolean isDetonates(int i, int j, int[][] bombs) {
        long x = bombs[j][0] - bombs[i][0], y = bombs[j][1] - bombs[i][1];
        return x * x + y * y <= (long) bombs[i][2] * bombs[i][2];
    }
}

题目代码出自LeetCode，请自行查阅。

反思&扩展

其他应用

• 选课的智慧：如何确定选课的顺序
• 寻找制高点：寻找制高点，抢占有利地形
• 合法的括号：从非法括号中寻找合法括号序列
• 数的右侧： 从树的侧边观察数的伟岸身躯

对比深度优先遍历算法，广度优先遍历算法在搜索所有答案的时候是采用由近及远的方式。先访问离起始点最近的点，再访问远一些的点，就好像先访问走一步可以到达的点，再访问走两步可以到达的点。