Dado un árbol con N vértices y N-1 aristas representadas por una array 2D edge[] , la tarea es encontrar el valor mínimo entre las distancias máximas de cualquier Node a todos los demás Nodes del árbol.
Ejemplos:
Entrada: N = 4, bordes[] = { {1, 2}, {2, 3}, {2, 4} }
Salida: 1
Explicación: El árbol tiene el siguiente aspecto.
2
/ | \
1 3 4
La distancia máxima de la casa número 1 a cualquier otro Node es 2.
La distancia máxima de la casa número 2 a cualquier otro Node es 1.
La distancia máxima de la casa número 3 a cualquier otro Node es 2.
La distancia máxima de la casa número 4 a cualquier otro Node es 2.
El mínimo entre estos es 1.Entrada: N = 10, bordes[] = { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} }
Salida: 5
Enfoque: este problema se puede resolver utilizando la primera búsqueda en profundidad basada en la siguiente idea:
Para cada Node, encuentre el Node más lejano y la distancia a ese Node. Luego encuentra el mínimo entre esos valores.
Siga los pasos mencionados a continuación para implementar la idea:
- Cree una array de distancia (digamos d[] ) donde d[i] almacena la distancia máxima a todos los demás Nodes desde el i- ésimo Node.
- Para cada Node presente en el árbol, considere cada uno de ellos como la fuente uno por uno:
- Marque la distancia de la fuente a la fuente como cero.
- Encuentre la distancia máxima de todos los demás Nodes desde la fuente.
- Encuentre el valor mínimo entre estas distancias máximas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to run DFS
void dfs(vector<int>& d, int node,
vector<vector<int> >& adj, int dist)
{
d[node] = dist;
// DFS call fro all its neighbours
for (auto child : adj[node]) {
if (dist + 1 < d[child])
dfs(d, child, adj, dist + 1);
}
}
// Function to find the minimum distance
int minDist(int N, vector<vector<int> >& edges)
{
int ans = INT_MAX;
// Creation of the adjacency matrix
vector<vector<int> > adj(N + 1);
for (auto u : edges) {
adj[u[0]].push_back(u[1]);
adj[u[1]].push_back(u[0]);
}
// Consider ith node as source
// in each iteration
for (int i = 1; i <= N; i++) {
// Distance array to store
// distance of all the nodes
// from source
vector<int> d(N + 1, INT_MAX);
// DFS traversal of the tree and store
// distance of all nodes from source
dfs(d, i, adj, 0);
int dist = 0;
// Find max distance from distance array
for (int j = 1; j <= N; j++)
dist = max(dist, d[j]);
// If distance found is smaller than ans
// then make ans equal to distance
ans = min(ans, dist);
}
// Return the minimum value
return ans;
}
// Driver Code
int main()
{
int N = 4;
vector<vector<int> > edges
= { { 1, 2 }, { 2, 3 }, { 2, 4 } };
// Function call
cout << minDist(N, edges);
return 0;
}
Java
// 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 fro 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;
// Creation of the adjacency matrix
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]);
}
// Consider ith node as source
// in each iteration
for (int i = 1; i <= N; i++) {
// Distance array to store
// distance of all the nodes
// from source
int[] d = new int[N + 1];
for (int j = 0; j <= N; j++)
d[j] = Integer.MAX_VALUE;
// DFS traversal of the tree and store
// distance of all nodes from source
dfs(d, i, adj, 0);
int dist = 0;
// Find max distance from distance array
for (int j = 1; j <= N; j++)
dist = Math.max(dist, d[j]);
// If distance found is smaller than ans
// then make ans equal to distance
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));
}
}
// This code is contributed by Lovely Jain
Python3
# Python code to implement the above approach # Function to run DFS import sys def dfs(d, node, adj, dist): d[node] = dist # DFS call fro 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): # Distance array to store # distance of all the nodes # from source d = [sys.maxsize for i in range(N+1)] # DFS traversal of the tree and store # distance of all nodes from source dfs(d, i, adj, 0) dist = 0 # Find max distance from distance array for j in range(1,N+1): dist = max(dist, d[j]) # If distance found is smaller than ans # then make ans equal to distance 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)) # This code is contributed by shinjanpatra
Javascript
<script>
// Javascript code to implement the above approach
// Function to run DFS
function dfs(d, node, adj, dist) {
d[node] = dist;
// DFS call fro all its neighbours
for (let child of adj[node]) {
if (dist + 1 < d[child])
dfs(d, child, adj, dist + 1);
}
}
// Function to find the minimum distance
function minDist(N, edges) {
let ans = Number.MAX_SAFE_INTEGER;
// Creation of the adjacency matrix
let adj = new Array(N + 1).fill(0).map(() => new Array());
for (let u of edges) {
adj[u[0]].push(u[1]);
adj[u[1]].push(u[0]);
}
// Consider ith node as source
// in each iteration
for (let i = 1; i <= N; i++) {
// Distance array to store
// distance of all the nodes
// from source
let d = new Array(N + 1).fill(Number.MAX_SAFE_INTEGER);
// DFS traversal of the tree and store
// distance of all nodes from source
dfs(d, i, adj, 0);
let dist = 0;
// Find max distance from distance array
for (let j = 1; j <= N; j++)
dist = Math.max(dist, d[j]);
// If distance found is smaller than ans
// then make ans equal to distance
ans = Math.min(ans, dist);
}
// Return the minimum value
return ans;
}
// Driver Code
let N = 4;
let edges = [[1, 2], [2, 3], [2, 4]];
// Function call
document.write(minDist(N, edges));
// This code is contributed by gfgking.
</script>
1
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA