Given a tree with N vertices and N-1 edges represented by a 2D array edges[], the task is to find the minimum value among the maximum distances from any node to all other nodes of the tree.
Examples:
Input: N = 4, edges[] = { {1, 2}, {2, 3}, {2, 4} }
Output: 1
Explanation: The Tree looks like the following.
2
/ | \
1 3 4
Maximum distance from house number 1 to any other node is 2.
Maximum distance from house number 2 to any other node is 1.
Maximum distance from house number 3 to any other node is 2.
Maximum distance from house number 4 to any other node is 2.
The minimum among these is 1.Input: N = 10, edges[] = { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} }
Output: 5
Approach: This problem can be solved using Depth First Search based on the following idea:
For each node find the farthest node and the distance to that node. Then find the minimum among those values.
Follow the steps mentioned below to implement the idea:
- Create a distance array (say d[]) where d[i] stores the maximum distance to all other nodes from the ith node.
- For every node present in the tree consider each of them as the source one by one:
- Mark the distance of the source from the source as zero.
- Find the maximum distance of all other nodes from the source.
- Find the minimum value among these maximum distances.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to run DFSvoid dfs(vector<int>& d, int node, vector<vector<int> >& adj, int dist){ d[node] = dist; // DFS call for all its neighbours for (auto child : adj[node]) { if (dist + 1 < d[child]) dfs(d, child, adj, dist + 1); }}// Function to find the minimum distanceint 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 Codeint 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 approachimport 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; // 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 DFSimport sysdef 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 distancedef 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 CodeN = 4edges = [[1, 2], [2, 3], [2, 4]]# Function callprint(minDist(N, edges))# This code is contributed by shinjanpatra |
C#
// C# code to implement the above approachusing System;using System.Collections;using System.Collections.Generic;public class GFG { // Function to run DFS static void dfs(int[] d, int node, List<int>[] adj, int dist) { d[node] = dist; // DFS call for all its neighbours foreach(int child in adj[node]) { if (dist + 1 < d[child]) dfs(d, child, adj, dist + 1); } } // Function to find the minimum distance static int minDist(int N, int[, ] edges) { int ans = Int32.MaxValue; // Creation of the adjacency matrix List<int>[] adj = new List<int>[ N + 1 ]; for (int i = 0; i <= N; i++) adj[i] = new List<int>(); for (int i = 0; i < edges.GetLength(0); i++) { int[] u = { edges[i, 0], edges[i, 1] }; 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] = Int32.MaxValue; // 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 Console.WriteLine(minDist(N, edges)); }}// This code is contributed by karandeep1234. |
Javascript
<script>// Javascript code to implement the above approach// Function to run DFSfunction dfs(d, node, adj, dist) { d[node] = dist; // DFS call for 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 distancefunction 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 Codelet N = 4;let edges = [[1, 2], [2, 3], [2, 4]];// Function calldocument.write(minDist(N, edges));// This code is contributed by gfgking.</script> |
Output
1
Time Complexity: O(N*N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
