Given a non-cyclic graph having V nodes and E edges and a source node S, the task is to calculate the sum of the minimum element at each level from source node S in the given graph.
Examples:
Input: S = 0, Below is the given graph
Output: 5
Explanation:
There is only one node at depth 0 i.e. 0.
At depth 1 there are 3 nodes 1, 2, 3, and minimum of them is 1.
At depth 2 there are another 3 nodes i.e. 6, 4, 5, and a minimum of them is 4.
So the sum of minimum element at each depth is 0 + 1 + 4 = 5.
Input: S = 2, Below is the given graph
Output: 8
Explanation:
At depth 0 only 1 node exists i.e. 2.
At depth 1 minimum element is 0.
At depth 2 minimum element is 1.
At depth 3 minimum element is 5
So the sum of minimum element at each depth is 2 + 0 + 1 + 5 = 8.
Approach: The idea is to use DFS Traversal. Below are the steps:
- Initialize an array(say arr[]) to store the minimum element at each level.
- Start the DFS Traversal from the given source node S with a variable depth(initially 0).
- Update the minimum value of current depth in the array arr[].
- Recursively recur for child node with incrementing the value of depth from the previous recursive call such that the minimum value at corresponding depth can be updated accordingly.
- After the above steps the sum of values stored in arr[] is the required total sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to add an edge in a graphvoid addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Variable to store depth of graphint max_depth = 0;// Function to know the depth of graphvoid find_depth(vector<int> adj[], vector<bool>& visited, int start, int depth){ // Mark the node start as true visited[start] = true; // Update the maximum depth max_depth = max(max_depth, depth); // Recur for the child node of // start node for (auto i : adj[start]) { if (!visited[i]) find_depth(adj, visited, i, depth + 1); }}// Function to calculate min value// at every depthvoid dfs(vector<int> adj[], int start, vector<bool>& visited, vector<int>& store_min_elements, int depth){ // marking already visited // vertices as true visited[start] = true; // Store the min value for // every depth store_min_elements[depth] = min(store_min_elements[depth], start); // Traverse Child node of start node for (auto i : adj[start]) { if (!visited[i]) dfs(adj, i, visited, store_min_elements, depth + 1); }}// Function to calculate the sumvoid minSum_depth(vector<int> adj[], int start, int total_nodes){ vector<bool> visited(total_nodes, false); // Calling function to know // the depth of graph find_depth(adj, visited, start, 0); // Set all value of visited // to false again fill(visited.begin(), visited.end(), false); // Declaring vector of // "max_depth + 1" size to // store min values at every // depth initialise vector // with max number vector<int> store_min_elements( max_depth + 1, INT_MAX); // Calling dfs function for // calculation of min element // at every depth dfs(adj, start, visited, store_min_elements, 0); // Variable to store sum of // all min elements int min_sum = 0; // Calculation of minimum sum for (int i = 0; i < store_min_elements.size(); i++) { min_sum += store_min_elements[i]; } // Print the minimum sum cout << min_sum << endl;}// Driver Codeint main(){ // Given Nodes and start node int V = 7, start = 0; // Given graph vector<int> adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 6); addEdge(adj, 2, 4); addEdge(adj, 3, 5); // Function Call minSum_depth(adj, start, V);} |
Java
// Java program for the above approach import java.io.*; import java.util.*;class Graph{ public static int V;// Variable to store depth of graphpublic static int max_depth = 0; private static LinkedList<Integer> adj[]; @SuppressWarnings("unchecked")Graph(int v) { V = v; adj = new LinkedList[v]; for(int i = 0; i < v; ++i) adj[i] = new LinkedList(); } static void addEdge(int v, int w) { adj[v].add(w); } static void find_depth(boolean visited[], int start, int depth) { // Mark the node start as true visited[start] = true; // Update the maximum depth max_depth = Math.max(max_depth, depth); // Recur for the child node of // start node Iterator<Integer> i = adj[start].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) find_depth(visited, n, depth + 1); }} // Function to calculate min value // at every depth static void dfs(int start, boolean visited[], int store_min_elements[], int depth) { // Marking already visited // vertices as true visited[start] = true; // Store the min value for // every depth store_min_elements[depth] = Math.min( store_min_elements[depth], start); // Traverse Child node of start node Iterator<Integer> i = adj[start].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) dfs(n, visited, store_min_elements, depth + 1); }} // Function to calculate the sum static void minSum_depth(int start, int total_nodes) { boolean visited[] = new boolean[total_nodes]; // Calling function to know // the depth of graph find_depth(visited, start, 0); // Set all value of visited // to false again Arrays.fill(visited, false); // Declaring vector of // "max_depth + 1" size to // store min values at every // depth initialise vector // with max number int store_min_elements[] = new int[max_depth + 1]; Arrays.fill(store_min_elements, Integer.MAX_VALUE); // Calling dfs function for // calculation of min element // at every depth dfs(start, visited, store_min_elements, 0); // Variable to store sum of // all min elements int min_sum = 0; // Calculation of minimum sum for(int i = 0; i < store_min_elements.length; i++) { min_sum += store_min_elements[i]; } // Print the minimum sum System.out.println(min_sum);} // Driver Code public static void main(String args[]) { // Given Nodes and start node V = 7; int start = 0; Graph g = new Graph(V); // Given graph g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(1, 6); g.addEdge(2, 4); g.addEdge(3, 5); // Function call minSum_depth( start, V); } } // This code is contributed by Stream_Cipher |
Python3
# Python program for the above approachclass Graph: def __init__(self, v): self.max_depth = 0 self.V = v self.adj = [] for i in range(v): self.adj.append([]) def addEdge(self, v, w): self.adj[v].append(w) def find_depth(self, visited, start, depth): # Mark the node start as true visited[start] = True # Update the maximum depth self.max_depth = max(self.max_depth, depth) # Recur for the child node of # start node for n in self.adj[start]: if (not visited[n]): self.find_depth(visited, n, depth + 1) # Function to calculate min value # at every depth def dfs(self, start, visited, store_min_elements, depth): # Marking already visited # vertices as true visited[start] = True # Store the min value for # every depth store_min_elements[depth] = min( store_min_elements[depth], start) # Traverse Child node of start node for n in self.adj[start]: if (not visited[n]): self.dfs(n, visited, store_min_elements, depth + 1) # Function to calculate the sum def minSum_depth(self, start, total_nodes): visited = [False]*total_nodes # Calling function to know # the depth of graph self.find_depth(visited, start, 0) # Set all value of visited # to false again visited = [False]*total_nodes # Declaring list of # "max_depth + 1" size to # store min values at every # depth initialise list # with max number store_min_elements = [10000000] * (self.max_depth + 1) # Calling dfs function for # calculation of min element # at every depth self.dfs(start, visited, store_min_elements, 0) # Variable to store sum of # all min elements min_sum = 0 # Calculation of minimum sum for i in range(len(store_min_elements)): min_sum += store_min_elements[i] # Print the minimum sum print(min_sum)# Driver Code# Given Nodes and start nodeV = 7start = 0g = Graph(V)# Given graphg.addEdge(0, 1)g.addEdge(0, 2)g.addEdge(0, 3)g.addEdge(1, 6)g.addEdge(2, 4)g.addEdge(3, 5)# Function callg.minSum_depth(start, V)# This code is contributed by Lovely Jain |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class Graph{ private static int V;private static int start;// Variable to store depth of graphpublic static int max_depth = 0; private static List<int>[] adj; Graph(int v) { V = v; adj = new List<int>[v]; for(int i = 0; i < v; ++i) adj[i] = new List<int>(); } // Function to add an edge in a graph void addEdge(int v, int w) { adj[v].Add(w); } // Function to know the depth of graphvoid find_depth(bool []visited, int start, int depth) { // Mark the node start as true visited[start] = true; // Update the maximum depth max_depth = Math.Max(max_depth, depth); // Recur for the child node of // start node List<int> vList = adj[start]; foreach(var n in vList) { if (!visited[n]) find_depth(visited, n, depth + 1); } } // Function to calculate min value // at every depth void dfs(int start, bool []visited, int []store_min_elements, int depth) { // Marking already visited // vertices as true visited[start] = true; // Store the min value for // every depth store_min_elements[depth] = Math.Min( store_min_elements[depth], start); // Traverse Child node of start node List<int> vList = adj[start]; foreach(var n in vList) { if (!visited[n]) dfs(n, visited, store_min_elements, depth + 1); } } // Function to calculate the sum void minSum_depth(int start, int total_nodes) { bool []visited = new bool[total_nodes]; // Calling function to know // the depth of graph find_depth(visited, start, 0); // Set all value of visited // to false again for(int i = 0; i < visited.Length; i++) { visited[i] = false; } // Declaring vector of "max_depth + 1" // size to store min values at every // depth initialise vector with max number int []store_min_elements = new int [max_depth + 1]; for(int i = 0; i < store_min_elements.Length; i++) { store_min_elements[i] = Int32.MaxValue; } // Calling dfs function for // calculation of min element // at every depth dfs(start, visited, store_min_elements, 0); // Variable to store sum of // all min elements int min_sum = 0; // Calculation of minimum sum for(int i = 0; i < store_min_elements.Length; i++) { min_sum += store_min_elements[i]; } // Print the minimum sum Console.WriteLine(min_sum);} // Driver Code public static void Main() { // Given Nodes and start node V = 7; start = 0; Graph g = new Graph(V); // Given graph g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(1, 6); g.addEdge(2, 4); g.addEdge(3, 5); // Function call g.minSum_depth(start , V); } } // This code is contributed by Stream_Cipher |
Javascript
<script>// JavaScript program for the above approach var V = 0;var start = 0;// Variable to store depth of graphvar max_depth = 0; var adj; function initialize( v) { V = v; adj = Array.from(Array(v), ()=>Array());} // Function to add an edge in a graph function addEdge(v, w) { adj[v].push(w); } // Function to know the depth of graphfunction find_depth(visited, start, depth) { // Mark the node start as true visited[start] = true; // Update the maximum depth max_depth = Math.max(max_depth, depth); // Recur for the child node of // start node var vList = adj[start]; for(var n of vList) { if (!visited[n]) find_depth(visited, n, depth + 1); } } // Function to calculate min value // at every depth function dfs(start, visited, store_min_elements, depth) { // Marking already visited // vertices as true visited[start] = true; // Store the min value for // every depth store_min_elements[depth] = Math.min( store_min_elements[depth], start); // Traverse Child node of start node var vList = adj[start]; for(var n of vList) { if (!visited[n]) dfs(n, visited, store_min_elements, depth + 1); } } // Function to calculate the sum function minSum_depth(start, total_nodes) { var visited = Array(total_nodes).fill(false); // Calling function to know // the depth of graph find_depth(visited, start, 0); // Set all value of visited // to false again for(var i = 0; i < visited.length; i++) { visited[i] = false; } // Declaring vector of "max_depth + 1" // size to store min values at every // depth initialise vector with max number var store_min_elements = Array(max_depth+1).fill(0); for(var i = 0; i < store_min_elements.length; i++) { store_min_elements[i] = 1000000000; } // Calling dfs function for // calculation of min element // at every depth dfs(start, visited, store_min_elements, 0); // Variable to store sum of // all min elements var min_sum = 0; // Calculation of minimum sum for(var i = 0; i < store_min_elements.length; i++) { min_sum += store_min_elements[i]; } // Print the minimum sum document.write(min_sum);} // Driver Code // Given Nodes and start nodeV = 7;start = 0; initialize(V); // Given graph addEdge(0, 1); addEdge(0, 2); addEdge(0, 3); addEdge(1, 6); addEdge(2, 4); addEdge(3, 5); // Function callminSum_depth(start , V); </script> |
Output:
5
Time Complexity: O(V + E)
Auxiliary Space: O(V)
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!
