Maximum sum of values of nodes among all connected components of an undirected graph
Given an undirected graph with V vertices and E edges. Every node has been assigned a given value. The task is to find the connected chain with the maximum sum of values among all the connected components in the graph.
Examples:
Input: V = 7, E = 4
Values = {10, 25, 5, 15, 5, 20, 0}
Output : Max Sum value = 35
Explanation:
Component {1, 2} – Value {10, 25}: sumValue = 10 + 25 = 35
Component {3, 4, 5} – Value {5, 15, 5}: sumValue = 5 + 15 + 5 = 25
Component {6, 7} – Value {20, 0}: sumValue = 20 + 0 = 20
Max Sum value chain is {1, 2} with values {10, 25}, hence 35 is answer.
Input: V = 10, E = 6
Values = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}Output : Max Sum value = 105
Approach: The idea is to use the Depth First Search traversal method to keep a track of all the connected components. A temporary variable is used to sum up all the values of the individual values of the connected chains. At each traversal of a connected component, the heaviest value till now is compared with the current value and updated accordingly. After all connected components have been traversed, the maximum among all will be the answer.
Below is the implementation of the above approach:
C++
// C++ program to find Maximum sum of values // of nodes among all connected // components of an undirected graph #include <bits/stdc++.h> using namespace std; // Function to implement DFS void depthFirst( int v, vector< int > graph[], vector< bool >& visited, int & sum, vector< int > values) { // Marking the visited vertex as true visited[v] = true ; // Updating the value of connection sum += values[v - 1]; // Traverse for all adjacent nodes for ( auto i : graph[v]) { if (visited[i] == false ) { // Recursive call to the DFS algorithm depthFirst(i, graph, visited, sum, values); } } } void maximumSumOfValues(vector< int > graph[], int vertices, vector< int > values) { // Initializing boolean array to mark visited vertices vector< bool > visited(values.size() + 1, false ); // maxChain stores the maximum chain size int maxValueSum = INT_MIN; // Following loop invokes DFS algorithm for ( int i = 1; i <= vertices; i++) { if (visited[i] == false ) { // Variable to hold temporary values int sum = 0; // DFS algorithm depthFirst(i, graph, visited, sum, values); // Conditional to update max value if (sum > maxValueSum) { maxValueSum = sum; } } } // Printing the heaviest chain value cout << "Max Sum value = " ; cout << maxValueSum << "\n" ; } // Driver function to test above function int main() { // Defining the number of edges and vertices int E = 4, V = 7; // Initializing graph in the form of adjacency list vector< int > graph[V+1]; // Assigning the values for each // vertex of the undirected graph vector< int > values; values.push_back(10); values.push_back(25); values.push_back(5); values.push_back(15); values.push_back(5); values.push_back(20); values.push_back(0); // Constructing the undirected graph graph[1].push_back(2); graph[2].push_back(1); graph[3].push_back(4); graph[4].push_back(3); graph[3].push_back(5); graph[5].push_back(3); graph[6].push_back(7); graph[7].push_back(6); maximumSumOfValues(graph, V, values); return 0; } |
Java
// Java program to find Maximum sum of // values of nodes among all connected // components of an undirected graph import java.util.*; class GFG{ static int sum; // Function to implement DFS static void depthFirst( int v, Vector<Integer> graph[], boolean []visited, Vector<Integer> values) { // Marking the visited vertex as true visited[v] = true ; // Updating the value of connection sum += values.get(v - 1 ); // Traverse for all adjacent nodes for ( int i : graph[v]) { if (visited[i] == false ) { // Recursive call to the DFS algorithm depthFirst(i, graph, visited, values); } } } static void maximumSumOfValues(Vector<Integer> graph[], int vertices, Vector<Integer> values) { // Initializing boolean array to // mark visited vertices boolean []visited = new boolean [values.size() + 1 ]; // maxChain stores the maximum chain size int maxValueSum = Integer.MIN_VALUE; // Following loop invokes DFS algorithm for ( int i = 1 ; i <= vertices; i++) { if (visited[i] == false ) { // Variable to hold temporary values sum = 0 ; // DFS algorithm depthFirst(i, graph, visited, values); // Conditional to update max value if (sum > maxValueSum) { maxValueSum = sum; } } } // Printing the heaviest chain value System.out.print( "Max Sum value = " ); System.out.print(maxValueSum + "\n" ); } // Driver code public static void main(String[] args) { // Initializing graph in the form // of adjacency list @SuppressWarnings ( "unchecked" ) Vector<Integer> []graph = new Vector[ 1001 ]; for ( int i = 0 ; i < graph.length; i++) graph[i] = new Vector<Integer>(); // Defining the number of edges and vertices int E = 4 , V = 7 ; // Assigning the values for each // vertex of the undirected graph Vector<Integer> values = new Vector<Integer>(); values.add( 10 ); values.add( 25 ); values.add( 5 ); values.add( 15 ); values.add( 5 ); values.add( 20 ); values.add( 0 ); // Constructing the undirected graph graph[ 1 ].add( 2 ); graph[ 2 ].add( 1 ); graph[ 3 ].add( 4 ); graph[ 4 ].add( 3 ); graph[ 3 ].add( 5 ); graph[ 5 ].add( 3 ); graph[ 6 ].add( 7 ); graph[ 7 ].add( 6 ); maximumSumOfValues(graph, V, values); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find Maximum sum # of values of nodes among all connected # components of an undirected graph import sys graph = [[] for i in range ( 1001 )] visited = [ False ] * ( 1001 + 1 ) sum = 0 # Function to implement DFS def depthFirst(v, values): global sum # Marking the visited vertex as true visited[v] = True # Updating the value of connection sum + = values[v - 1 ] # Traverse for all adjacent nodes for i in graph[v]: if (visited[i] = = False ): # Recursive call to the # DFS algorithm depthFirst(i, values) def maximumSumOfValues(vertices,values): global sum # Initializing boolean array to # mark visited vertices # maxChain stores the maximum chain size maxValueSum = - sys.maxsize - 1 # Following loop invokes DFS algorithm for i in range ( 1 , vertices + 1 ): if (visited[i] = = False ): # Variable to hold temporary values # sum = 0 # DFS algorithm depthFirst(i, values) # Conditional to update max value if ( sum > maxValueSum): maxValueSum = sum sum = 0 # Printing the heaviest chain value print ( "Max Sum value = " , end = "") print (maxValueSum) # Driver code if __name__ = = '__main__' : # Initializing graph in the # form of adjacency list # Defining the number of # edges and vertices E = 4 V = 7 # Assigning the values for each # vertex of the undirected graph values = [] values.append( 10 ) values.append( 25 ) values.append( 5 ) values.append( 15 ) values.append( 5 ) values.append( 20 ) values.append( 0 ) # Constructing the undirected graph graph[ 1 ].append( 2 ) graph[ 2 ].append( 1 ) graph[ 3 ].append( 4 ) graph[ 4 ].append( 3 ) graph[ 3 ].append( 5 ) graph[ 5 ].append( 3 ) graph[ 6 ].append( 7 ) graph[ 7 ].append( 6 ) maximumSumOfValues(V, values) # This code is contributed by mohit kumar 29 |
C#
// C# program to find Maximum sum of // values of nodes among all connected // components of an undirected graph using System; using System.Collections.Generic; class GFG{ static int sum; // Function to implement DFS static void depthFirst( int v, List< int > []graph, bool []visited, List< int > values) { // Marking the visited vertex as true visited[v] = true ; // Updating the value of connection sum += values[v - 1]; // Traverse for all adjacent nodes foreach ( int i in graph[v]) { if (visited[i] == false ) { // Recursive call to the DFS algorithm depthFirst(i, graph, visited, values); } } } static void maximumSumOfValues(List< int > []graph, int vertices, List< int > values) { // Initializing bool array to // mark visited vertices bool []visited = new bool [values.Count + 1]; // maxChain stores the maximum chain size int maxValueSum = int .MinValue; // Following loop invokes DFS algorithm for ( int i = 1; i <= vertices; i++) { if (visited[i] == false ) { // Variable to hold temporary values sum = 0; // DFS algorithm depthFirst(i, graph, visited, values); // Conditional to update max value if (sum > maxValueSum) { maxValueSum = sum; } } } // Printing the heaviest chain value Console.Write( "Max Sum value = " ); Console.Write(maxValueSum + "\n" ); } // Driver code public static void Main(String[] args) { // Initializing graph in the form // of adjacency list List< int > []graph = new List< int >[1001]; for ( int i = 0; i < graph.Length; i++) graph[i] = new List< int >(); // Defining the number of edges and vertices int V = 7; // Assigning the values for each // vertex of the undirected graph List< int > values = new List< int >(); values.Add(10); values.Add(25); values.Add(5); values.Add(15); values.Add(5); values.Add(20); values.Add(0); // Constructing the undirected graph graph[1].Add(2); graph[2].Add(1); graph[3].Add(4); graph[4].Add(3); graph[3].Add(5); graph[5].Add(3); graph[6].Add(7); graph[7].Add(6); maximumSumOfValues(graph, V, values); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program to find Maximum sum // of values of nodes among all connected // components of an undirected graph let graph = new Array(1001); for (let i=0;i<1001;i++){ graph[i] = new Array(); } let visited = new Array(1001+1).fill( false ); let sum = 0 // Function to implement DFS function depthFirst(v, values){ // Marking the visited vertex as true visited[v] = true // Updating the value of connection sum += values[v - 1] // Traverse for all adjacent nodes for (let i of graph[v]){ if (visited[i] == false ){ // Recursive call to the // DFS algorithm depthFirst(i, values) } } } function maximumSumOfValues(vertices,values){ // Initializing boolean array to // mark visited vertices // maxChain stores the maximum chain size let maxValueSum = Number.MIN_VALUE // Following loop invokes DFS algorithm for (let i=1;i<vertices + 1;i++){ if (visited[i] == false ){ // Variable to hold temporary values // sum = 0 // DFS algorithm depthFirst(i, values) // Conditional to update max value if (sum > maxValueSum) maxValueSum = sum sum = 0 } } // Printing the heaviest chain value document.write( "Max Sum value = " , "" ) document.write(maxValueSum) } // Driver code // Initializing graph in the // form of adjacency list // Defining the number of // edges and vertices let E = 4 let V = 7 // Assigning the values for each // vertex of the undirected graph let values = [] values.push(10) values.push(25) values.push(5) values.push(15) values.push(5) values.push(20) values.push(0) // Constructing the undirected graph graph[1].push(2) graph[2].push(1) graph[3].push(4) graph[4].push(3) graph[3].push(5) graph[5].push(3) graph[6].push(7) graph[7].push(6) maximumSumOfValues(V, values) // This code is contributed by shinjanpatra </script> |
Max Sum value = 35
Time Complexity: O(E + V)
Auxiliary Space: O(E + V)
Approach 2 :- Using Breadth Frirst Search (BFS) Technique
- First we create boolean array visited to keep track of visited vertices
- Next , we will traverse through every vertex if it is not visted and we calculate the sum of the connected components of current vertex using BFS.
- Next , we will update the max with currentcomponentsum of every vertex.
- so ,Finally the max variable will be storing the maximum component sum .
- In breadthFirstSearch function , we first mark the vertex as visited.
- Then we will add that vertex in the Queue Datastructure.
- Next , we will travers through its adjacent vertices and add them into the queue and marking every adjacent vertex as visited.
- Next , we will calculate the total componet sum by adding the values of every visited vertex.
- Finally, we will return the total component sum .
Below is the Implementation of the BFS Approach :-
C++
#include <iostream> #include <vector> #include <queue> #include <climits> // Include the header for INT_MIN using namespace std; // Function to implement BFS int breadthFirst( int v, vector< int > graph[], bool visited[], vector< int >& values) { // Initially sum will be assigned to zero int sum = 0; // Marking the vertex as visited visited[v] = true ; queue< int > q; // Adding the current vertex in the queue data structure q.push(v); while (!q.empty()) { // Polling the current vertex and adding its value to the sum int node = q.front(); q.pop(); sum += values[node - 1]; // Traversing its adjacent vertices for ( int it : graph[node]) { // If the vertex is not visited, we add it into the queue and mark the vertex as visited if (!visited[it]) { q.push(it); visited[it] = true ; } } } // Return the sum return sum; } void maximumSumOfValues(vector< int > graph[], int vertices, vector< int >& values) { // Creating a boolean array to mark the visited nodes bool visited[vertices + 1] = { false }; // Initializing maxSum with INT_MIN int maxSum = INT_MIN; // Traversing through each vertex for ( int i = 1; i <= vertices; i++) { // If the current vertex is not visited, apply BFS to find the component sum with its adjacent nodes if (!visited[i]) { int currentComponentSum = breadthFirst(i, graph, visited, values); // Updating maxSum with currentComponentSum maxSum = max(maxSum, currentComponentSum); } } // Finally, printing the max component sum cout << "Max Sum Value = " << maxSum << endl; } int main() { // Initializing the graph in the form of an adjacency list vector< int > graph[1001]; // Defining the number of edges and vertices int E = 6, V = 10; // Assigning values for each vertex of the undirected graph vector< int > values = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}; // Constructing the undirected graph graph[2].push_back(3); graph[3].push_back(2); graph[3].push_back(4); graph[4].push_back(3); graph[4].push_back(5); graph[5].push_back(4); graph[6].push_back(7); graph[7].push_back(6); graph[7].push_back(8); graph[8].push_back(7); graph[9].push_back(10); graph[10].push_back(9); maximumSumOfValues(graph, V, values); return 0; } // This code is contributed by shivamgupta0987654321 |
Java
// Java program to find Maximum sum of // values of nodes among all connected // components of an undirected graph import java.util.*; class Main { // Function to implement BFS static int breadthFirst( int v, Vector<Integer> graph[], boolean [] visited, Vector<Integer> values) { // Iniatially sum will be assigned to zero int sum = 0 ; // marking the vertex as visited visited[v] = true ; Queue<Integer> q = new LinkedList<>(); // Adding the current vertex in the queue // datastructure q.add(v); while (!q.isEmpty()) { // polling the current vertex and adding its // value to the sum int node = q.poll(); sum += values.get(node - 1 ); // Traversing its adjacent vertices for ( int it : graph[node]) { // if the vertex is not visited // we add it into the queue and // mark the vertex as visited if (visited[it] == false ) { q.add(it); visited[it] = true ; } } } // return the sum return sum; } static void maximumSumOfValues(Vector<Integer> graph[], int vertices, Vector<Integer> values) { // creating boolean array to mark the visited nodes boolean visited[] = new boolean [vertices + 1 ]; // Initailizing max with Integer_MINVALUE; int max = Integer.MIN_VALUE; // Traversing through each vertex for ( int i = 1 ; i < vertices + 1 ; i++) { // if the current vertex is not visited // we will apply bfs to the vertex to find // the component sum with its adjacent nodes if (visited[i] == false ) { int currentComponentSum = breadthFirst( i, graph, visited, values); // updating max with currentComponentSum max = Math.max(max, currentComponentSum); } } // finally printing the max componentSum System.out.print( "Max Sum Value = " + max); } // Driver code public static void main(String[] args) { // Initializing graph in the form // of adjacency list @SuppressWarnings ( "unchecked" ) Vector<Integer>[] graph = new Vector[ 1001 ]; for ( int i = 0 ; i < graph.length; i++) graph[i] = new Vector<Integer>(); // Defining the number of edges and vertices int E = 6 , V = 10 ; // Assigning the values for each // vertex of the undirected graph Vector<Integer> values = new Vector<Integer>(); values.add( 5 ); values.add( 10 ); values.add( 15 ); values.add( 20 ); values.add( 25 ); values.add( 30 ); values.add( 35 ); values.add( 40 ); values.add( 45 ); values.add( 50 ); // Constructing the undirected graph graph[ 2 ].add( 3 ); graph[ 3 ].add( 2 ); graph[ 3 ].add( 4 ); graph[ 4 ].add( 3 ); graph[ 4 ].add( 5 ); graph[ 5 ].add( 4 ); graph[ 6 ].add( 7 ); graph[ 7 ].add( 6 ); graph[ 7 ].add( 8 ); graph[ 8 ].add( 7 ); graph[ 9 ].add( 10 ); graph[ 10 ].add( 9 ); maximumSumOfValues(graph, V, values); } } // This code is contributed by srimann7 |
Python3
from queue import Queue # Function to implement BFS def breadth_first(v, graph, visited, values): # Initially sum will be assigned to zero sum_value = 0 # Marking the vertex as visited visited[v] = True q = Queue() # Adding the current vertex in the queue data structure q.put(v) while not q.empty(): # Polling the current vertex and adding its value to the sum node = q.get() sum_value + = values[node - 1 ] # Traversing its adjacent vertices for neighbor in graph[node]: # If the vertex is not visited, we add it into the queue and mark the vertex as visited if not visited[neighbor]: q.put(neighbor) visited[neighbor] = True # Return the sum return sum_value def maximum_sum_of_values(graph, vertices, values): # Creating a boolean array to mark the visited nodes visited = [ False ] * (vertices + 1 ) # Initializing max_sum with negative infinity max_sum = float ( '-inf' ) # Traversing through each vertex for i in range ( 1 , vertices + 1 ): # If the current vertex is not visited, apply BFS to find the component # sum with its adjacent nodes if not visited[i]: current_component_sum = breadth_first(i, graph, visited, values) # Updating max_sum with current_component_sum max_sum = max (max_sum, current_component_sum) # Finally, printing the max component sum print ( "Max Sum Value =" , max_sum) # Driver Code if __name__ = = "__main__" : # Initializing the graph in the form of an adjacency list graph = [[] for _ in range ( 1001 )] # Defining the number of edges and vertices E, V = 6 , 10 # Assigning values for each vertex of the undirected graph values = [ 5 , 10 , 15 , 20 , 25 , 30 , 35 , 40 , 45 , 50 ] # Constructing the undirected graph graph[ 2 ].extend([ 3 ]) graph[ 3 ].extend([ 2 , 4 ]) graph[ 4 ].extend([ 3 , 5 ]) graph[ 5 ].extend([ 4 ]) graph[ 6 ].extend([ 7 ]) graph[ 7 ].extend([ 6 , 8 ]) graph[ 8 ].extend([ 7 ]) graph[ 9 ].extend([ 10 ]) graph[ 10 ].extend([ 9 ]) maximum_sum_of_values(graph, V, values) # This code is contributed by shivamgupta310570 |
C#
using System; using System.Collections.Generic; class Program { // Function to implement BFS static int BreadthFirst( int v, List<List< int >> graph, bool [] visited, int [] values) { // Initially sum will be assigned to zero int sumValue = 0; // Marking the vertex as visited visited[v] = true ; Queue< int > q = new Queue< int >(); // Adding the current vertex in the queue data structure q.Enqueue(v); while (q.Count > 0) { // Polling the current vertex and adding its value to the sum int node = q.Dequeue(); sumValue += values[node - 1]; // Traversing its adjacent vertices foreach ( int neighbor in graph[node]) { // If the vertex is not visited, we add it into the queue and mark the vertex as visited if (!visited[neighbor]) { q.Enqueue(neighbor); visited[neighbor] = true ; } } } // Return the sum return sumValue; } static void MaximumSumOfValues(List<List< int >> graph, int vertices, int [] values) { // Creating a boolean array to mark the visited nodes bool [] visited = new bool [vertices + 1]; // Initializing maxSum with negative infinity int maxSum = int .MinValue; // Traversing through each vertex for ( int i = 1; i <= vertices; i++) { // If the current vertex is not visited, apply BFS to find the component // sum with its adjacent nodes if (!visited[i]) { int currentComponentSum = BreadthFirst(i, graph, visited, values); // Updating maxSum with currentComponentSum maxSum = Math.Max(maxSum, currentComponentSum); } } // Finally, printing the max component sum Console.WriteLine( "Max Sum Value = " + maxSum); } // Driver Code static void Main() { // Initializing the graph in the form of an adjacency list List<List< int >> graph = new List<List< int >>(1001); for ( int i = 0; i < 1001; i++) { graph.Add( new List< int >()); } // Defining the number of vertices int V = 10; // Assigning values for each vertex of the undirected graph int [] values = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 }; // Constructing the undirected graph graph[2].Add(3); graph[3].AddRange( new [] { 2, 4 }); graph[4].AddRange( new [] { 3, 5 }); graph[5].Add(4); graph[6].Add(7); graph[7].AddRange( new [] { 6, 8 }); graph[8].Add(7); graph[9].Add(10); graph[10].Add(9); MaximumSumOfValues(graph, V, values); } } |
Javascript
// JavaScript program for the above approach // Function to implement BFS function breadthFirst(v, graph, visited, values) { // Initially sum will be assigned to zero let sum = 0; // Marking the vertex as visited visited[v] = true ; let queue = []; // Adding the current vertex in the queue data structure queue.push(v); while (queue.length !== 0) { // Polling the current vertex and adding its value to the sum let node = queue.shift(); sum += values[node - 1]; // Traversing its adjacent vertices for (let it of graph[node]) { // If the vertex is not visited, we add it into the // queue and mark the vertex as visited if (!visited[it]) { queue.push(it); visited[it] = true ; } } } // Return the sum return sum; } function maximumSumOfValues(graph, vertices, values) { // Creating a boolean array to mark the visited nodes let visited = new Array(vertices + 1).fill( false ); // Initializing maxSum with INT_MIN let maxSum = Number.MIN_SAFE_INTEGER; // Traversing through each vertex for (let i = 1; i <= vertices; i++) { // If the current vertex is not visited, apply BFS to find the // component sum with its adjacent nodes if (!visited[i]) { let currentComponentSum = breadthFirst(i, graph, visited, values); // Updating maxSum with currentComponentSum maxSum = Math.max(maxSum, currentComponentSum); } } // Finally, printing the max component sum console.log( "Max Sum Value =" , maxSum); } // Initializing the graph in the form of an adjacency list let graph = new Array(1001).fill().map(() => []); // Defining the number of edges and vertices let E = 6, V = 10; // Assigning values for each vertex of the undirected graph let values = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]; // Constructing the undirected graph graph[2].push(3); graph[3].push(2); graph[3].push(4); graph[4].push(3); graph[4].push(5); graph[5].push(4); graph[6].push(7); graph[7].push(6); graph[7].push(8); graph[8].push(7); graph[9].push(10); graph[10].push(9); maximumSumOfValues(graph, V, values); // This code is contributed by Susobhan Akhuli |
Max Sum Value = 105
Time Complexity :- O(V + E) , where V is number of vertices and E is number of edges.
Space Complexity :- O(V + E) , where V is number of vertices and E is number of edges.