给定一棵具有N个顶点和N-1 个边（由 2D 数组Edges[]表示）的树，任务是找到从任意节点到树的所有其他节点的最大距离中的最小值。
例子：
输入： N = 4, Edges[] = { {1, 2}, {2, 3}, {2, 4} }
输出： 1
解释：树如下所示。
- 节点 1 到任何其他节点的最大距离为 2。
- 节点 2 到任何其他节点的最大距离为 1。
- 节点 3 到任何其他节点的最大距离为 2。
- 节点 4 到任何其他节点的最大距离为 2。
其中最小值为 1。
输入： N = 10，edges[] = { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} }
输出： 5
方法：
这个问题可以使用深度优先搜索来解决，基于以下思想：
对于每个节点，找到最远的节点以及到该节点的距离。然后找到这些值中的最小值。
请按照下面提到的步骤来实现这个想法：
- 创建一个距离数组（例如d[]），其中d存储从第 i个节点到所有其他节点的最大距离。
- 对于树中存在的每个节点，将它们一一视为源：
- 将源与源的距离标记为零。
- 找出所有其他节点距源的最大距离。
- 找出这些最大距离中的最小值。
// Java code to implement the above approach
import java.util.ArrayList;
public class GFG {
// Function to run DFS
static void dfs(int[] d, int node,
ArrayList<Integer>[] adj, int dist)
{
d[node] = dist;
// DFS call for all its neighbours
for (int child : adj[node]) {
if (dist + 1 < d[child])
dfs(d, child, adj, dist + 1);
}
}
// Function to find the minimum distance
@SuppressWarnings("unchecked")
static int minDist(int N, int[][] edges)
{
int ans = Integer.MAX_VALUE;
// 创建邻接矩阵
ArrayList<Integer>[] adj = new ArrayList[N + 1];
for (int i = 0; i <= N; i++)
adj[i] = new ArrayList<Integer>();
for (int[] u : edges) {
adj[u[0]].add(u[1]);
adj[u[1]].add(u[0]);
}
// 将第 i 个节点视为源节点
// 在每次迭代中
for (int i = 1; i <= N; i++) {
//要存储的距离数组
//所有节点的距离
//来自源的距离
//来自源的距离
int[] d = new int[N + 1];
for (int j = 0; j <= N; j++)
d[j] = Integer.MAX_VALUE;
// DFS 遍历树和存储
// 所有节点与源点的距离
dfs(d, i, adj, 0);
int dist = 0;
// 从距离数组中找出最大距离
for (int j = 1; j <= N; j++)
dist = Math.max(dist, d[j]);
// 如果找到的距离小于答案
// 则使答案等于距离。
ans = Math.min(ans, dist);
}
// Return the minimum value
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
int[][] edges = { { 1, 2 }, { 2, 3 }, { 2, 4 } };
// Function call
System.out.println(minDist(N, edges));
}
}
|
Python：
# Python code to implement the above approach
# Function to run DFS
import sys
def dfs(d, node, adj, dist):
d[node] = dist
# DFS call for all its neighbours
for child in adj[node]:
if (dist + 1 < d[child]):
dfs(d, child, adj, dist + 1)
# Function to find the minimum distance
def minDist(N, edges):
ans = sys.maxsize
# Creation of the adjacency matrix
adj = [[] for i in range(N+1)]
for u in edges:
adj[u[0]].append(u[1])
adj[u[1]].append(u[0])
# Consider ith node as source
# in each iteration
for i in range(1,N+1):
# 要存储的距离数组
# 所有节点的距离
# 从源点到源点的距离
# 从源点到源点的距离
d = [sys.maxsize for i in range(N+1)]
# DFS 遍历树并存储
# 所有节点与源点的距离
dfs(d, i, adj, 0)
dist = 0
# 从距离数组中找出最大距离
for j in range(1,N+1):
dist = max(dist, d[j])
# 如果找到的距离小于答案
# 则使答案等于距离
ans = min(ans, dist)
# Return the minimum value
return ans
# Driver Code
N = 4
edges = [[1, 2], [2, 3], [2, 4]]
# Function call
print(minDist(N, edges))
|