华为OD机试 - 最长广播效应 - 广度优先搜索BFS（Java 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某通信网络中有N个网络结点，用1到N进行标识。
网络中的结点互联互通，且结点之间的消息传递有时延，相连结点的时延均为一个时间单位。
现给定网络结点的连接关系link[i]={u，v}，其中u和v表示网络结点。
当指定一个结点向其他结点进行广播，所有被广播结点收到消息后都会在原路径上回复一条响应消息，请计算发送结点至少需要等待几个时间单位才能收到所有被广播结点的响应消息。

注：

N的取值范围为[1，100];
连接关系link的长度不超过3000，且1 <= u,v <= N;
网络中任意结点间均是可达的;

二、输入描述

输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度T；
接下来的T行输入，表示结点间的连接关系列表；
最后一行的输入为一个正整数，表示指定的广播结点序号；

三、输出描述

输出一个整数，表示发送结点接收到所有响应消息至少需要等待的时长。

1、输入

5 7
1 4
2 1
2 3
2 4
3 4
3 5
4 5
2

2、输出

3、说明

结点2到5的最小时延为2，到剩余结点的最小时延均为1，所以至少要等待2*2=4s。

四、解题思路

核心思想

找到距离起点最远的点
找到到达最远的点的最短路径

这是一道典型的BFS算法题。

BFS（广度优先搜索）是一种图遍历算法，它从一个起始点开始，逐层扩展搜索范围，直到找到目标节点为止。

这种算法通常用于解决“最短路径”问题，比如在迷宫中找到从起点到终点的最短路径

首先，你会从起点开始，检查所有与它相邻的位置，也就是距离起点为1的位置；
然后，你会继续向外扩展，检查所有距离起点为2的位置，以此类推，直到找到出口。

在BFS中，你可以使用队列来存储待搜索的节点。起始点首先加入队列中，然后不断从队列中取出节点，检查它是否是目标节点。如果不是，就将它的所有未被访问过的邻居加入队列中。这样，队列中的节点总是按照它们距离起点的距离排序，先加入队列的节点总是先被取出来搜索。

通过这种方式，BFS可以找到起点到目标节点的最短路径。在实际应用中，BFS还可以用于拓扑排序、连通性检测等问题的解决。

五、Java算法源码

java">public class Test05 {
    // 找到起始点到其它节点的最短路径的最大值乘2即可
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /**
         * 1. 找到距离起点最远的点
         * 2. 找到到达最远的点的最短路径
         */
        int[] input1 = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 网络结点的个数N
        int N = input1[0];
        // 时延列表的长度T
        int T = input1[1];
        Map<Integer, Set<Integer>> setMap = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < T; i++) {
            int[] temp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            set.add(temp[0]);
            set.add(temp[1]);
            Set<Integer> tempSet = setMap.getOrDefault(temp[0], new HashSet<Integer>());
            tempSet.add(temp[1]);
            setMap.put(temp[0], tempSet);
        }

        Integer[] arr = new Integer[N];
        set.toArray(arr);
        Arrays.sort(arr);

        int target = Integer.valueOf(sc.nextLine());
        // 找到距离起点最远的点
        int max = target - arr[0] > arr[N - 1] - target ? arr[0] : arr[N - 1];
        dfs(setMap, target, max, 0);
    }

    private static void dfs(Map<Integer, Set<Integer>> setMap, int target, int max, int step) {
        if (target == max) {
            System.out.println(step * 2);
            return;
        }
        Set<Integer> targetSet = setMap.get(target);
        Integer[] arr1 = new Integer[targetSet.size()];
        targetSet.toArray(arr1);
        Arrays.sort(arr1);
        // target能直达的最大点
        int targetToMax = arr1[targetSet.size() - 1];
        step++;
        dfs(setMap, targetToMax, max, step);
    }
}