题目描述

在公司机房中，有 $n$ 台交换机以树形结构连接，交换机的编号从 $1$ 到 $n$。管理员希望选择一台交换机作为公网接入点（即树的根节点），使得这台交换机到其他任意交换机的最大跳数最小。请计算并输出这个最小的最大跳数。

思路

在树形结构中，最远的两点之间的路径长度称为树的直径。为了使根节点到其他所有节点的最大跳数最小，应将根节点放在直径的中间位置（即树的中心）。这样，根节点到最远节点的距离就是直径的一半，可能为整数或半整数。由于跳数必须是整数，所以我们取整数部分再加一，即最小的最大跳数为 (直径 + 1) / 2。因此，把边权设置为1，树形dp或者dfs,bfs求树的直径，答案为(树的直径+1)/2，这里提供bfs解法

cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 定义常量表示最大节点数量
const int MAXN = 100005;

// 邻接表存储树
vector<int> adj[MAXN];

// BFS 函数，返回最远的节点和距离
pair<int, int> bfs(int start, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    int far_node = start;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[far_node]) {
                    far_node = v;
                }
            }
        }
    }
    return {far_node, dist[far_node]};
}

int main() {
    int n;
    cin >> n;

    // 读取边信息，构建邻接表
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 第一次 BFS，找到最远的节点 u
    auto p1 = bfs(1, n);

    // 第二次 BFS，从节点 u 出发，找到最远的节点 v
    auto p2 = bfs(p1.first, n);

    // 计算半径
    int diameter = p2.second;
    int radius = (diameter + 1) / 2;

    // 输出结果
    cout << radius << endl;

    return 0;
}

python

import sys
import threading
def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        x, y = map(int, sys.stdin.readline().split())
        adj[x].append(y)
        adj[y].append(x)

    from collections import deque

    def bfs(start):
        dist = [-1] * (n + 1)
        q = deque()
        q.append(start)
        dist[start] = 0
        far_node = start
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
                    if dist[v] > dist[far_node]:
                        far_node = v
        return far_node, dist[far_node]

    u, _ = bfs(1)
    v, diameter = bfs(u)
    radius = (diameter + 1) // 2
    print(radius)

threading.Thread(target=main).start()

java

import java.util.*;
public class Main {
    static List<Integer>[] adj;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        adj = new ArrayList[n + 1];
        for(int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for(int i = 0; i < n -1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            adj[x].add(y);
            adj[y].add(x);
        }

        int[] p1 = bfs(1);
        int[] p2 = bfs(p1[0]);

        int diameter = p2[1];
        int radius = (diameter + 1) / 2;
        System.out.println(radius);
    }

    // BFS 函数，返回最远的节点和距离
    static int[] bfs(int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        dist[start] = 0;
        int far_node = start;

        while(!q.isEmpty()) {
            int u = q.poll();
            for(int v : adj[u]) {
                if(dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                    if(dist[v] > dist[far_node]) {
                        far_node = v;
                    }
                }
            }
        }
        return new int[]{far_node, dist[far_node]};
    }
}

题目内容

公司机房内由多台交换机树状组网，当前管理员想从这些交换机中选择一台起点交换机作为公网接入点，要求起点交换机到其他交换机最大跳数最小，请输出这个跳数最小值。

例如，当下面第一张图选取 $3$ 号交换机作为起点交换机时，$3$ 号交换机到 $1$ 号和 $4$ 号交换机跳数为 $1$ ，到 $2$ 号、 $5$ 号和 $6$ 号交换机跳数为 $2$ ，则跳数最小值为 $2$ 。

输入描述

第一行一个正整数 $n(1 ≤n ≤ 10^5)$，表示 $n$ 个交换机的编号从 $1$ 到 $n$ 。

接下来 $n-1$ 行每行两个正整数 ,$x,y(1≤x,y≤n)$,表示有一 条连接 $x,y$ 的边。

输出描述

一个正整数表示跳数最小值。

样例1

输入

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

输出

2

说明

请参考题目描述第一张图， $3$ 号交换机作为树的根节点后，树的深度为 $2$ 。

样例2

输入

8
1 2
1 3
3 4
3 5
5 6
5 7
7 8

输出

3

说明

请参考题目描述第二张图，选择 $3$ 号或 $5$ 号交换机作为树的根节点后，树的深度为 $3$ 。