dfs，参考leetcode 二叉树直径

经过多叉树某结点的最大直径是其最大两个子树直径+1

from collections import defaultdict

n = int(input())
graph = defaultdict(list)

for _ in range(n-1):
    line = list(map(int, input().split()))
    if not line:
        break
    node_1, node_2 = line
    graph[node_1].append(node_2)
    graph[node_2].append(node_1)


visited = [0] * (n+1)
global_diameter = 0

def dfs(node):
    global global_diameter, visited, graph
    if not node:
        return 0
    
    visited[node] = 1
    tmp_max_dias = [0, 0]
    for son_node in graph[node]:
        if visited[son_node] == 0:
            tmp_depth = dfs(son_node)
            if tmp_depth > min(tmp_max_dias):
                tmp_max_dias.pop(tmp_max_dias.index(min(tmp_max_dias)))
                tmp_max_dias.append(tmp_depth)

    global_diameter =  max(global_diameter, sum(tmp_max_dias) + 1)

    return max(tmp_max_dias) + 1


dfs(1)

print(global_diameter // 2)

枚举各个节点为根节点的直径 找最大值

#include <bits/stdc++.h>
using namespace std;

int global_max = 0;

int findRad(vector<vector<int>>& tree, int node, int parent) {
    int n = tree[node].size();
    int node_len = 0;
    for(int i=0;i<n; i++) {
        if(tree[node][i] == parent) continue;
        int child_len = findRad(tree, tree[node][i], node) +1;
        global_max = max(global_max, node_len+child_len);
        node_len = max(node_len, child_len);
    }
    return node_len;
}

int main() {
    int n;
    cin>>n;
    vector<vector<int>> tree(n+1,vector<int>{});
    for(int i=0; i<n; i++) {
        int x,y;
        cin>>x>>y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    findRad(tree, 1,-1);
    cout<<(global_max+1)/2;
    return 0;
}

from collections import defaultdict, deque


class DFSTree:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self, node, parent):
        max_distance = (0, node)
        for child in self.graph[node]:
            if child != parent:
                distance = self.dfs(child, node)
                max_distance = max(max_distance, (distance[0]+1, distance[1]))

        return max_distance

    def max_hop(self):
        # 第一次dfs找到最远的点
        _, farthest_node = self.dfs(1, -1)
        # 第二次dfs从最远的点出发找最远的距离
        diameter, _ = self.dfs(farthest_node, -1)
        radius = (diameter+1)//2

        return radius


class BFSTree(DFSTree):
    def __init__(self):
        super().__init__()

    def bfs(self, start):
        queue = deque([(0, start)])
        farthest_node = start
        visited = {start}
        max_distance = 0
        while queue:
            distance, cur_node = queue.popleft()
            if distance > max_distance:
                max_distance = distance
                farthest_node = cur_node
            for child in self.graph[cur_node]:
                if child not in visited:
                    visited.add(child)
                    queue.append((distance+1, child))

        return max_distance, farthest_node

    def max_hop(self):
        _, farthest_node = self.bfs(1)
        diameter, _ = self.bfs(farthest_node)
        radius = (diameter+1)//2

        return radius

def main1():
    n = int(input())
    dfs_tree = DFSTree()
    for i in range(n-1):
        p, c = map(int, input().split())
        dfs_tree.add_edge(p, c)
    print(dfs_tree.max_hop())

def main2():
    n = int(input())
    bfs_tree = BFSTree()
    for i in range(n-1):
        p, c = map(int, input().split())
        bfs_tree.add_edge(p, c)
    print(bfs_tree.max_hop())


if __name__ == "__main__":
    # main1()
    main2()

题目描述

在公司机房中，有 $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]};
    }
}