Dado un grafo no dirigido con V vértices y E aristas. A cada Node se le ha asignado un valor dado. La tarea es encontrar la string conectada con la suma máxima de valores entre todos los componentes conectados en el gráfico.
Ejemplos:
Entrada: V = 7, E = 4
Valores = {10, 25, 5, 15, 5, 20, 0}
Salida: Max Sum value = 35
Explicación:
Componente {1, 2} – Valor {10, 25}: sumValue = 10 + 25 = 35
Componente {3, 4, 5} – Valor {5, 15, 5}: sumValue = 5 + 15 + 5 = 25
Componente {6, 7} – Valor {20, 0}: sumValue = 20 + 0 = 20 La
string de valor Max Sum es {1, 2} con valores {10, 25}, por lo tanto, 35 es la respuesta .
Entrada: V = 10, E = 6
Valores = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}Salida: valor de suma máxima = 105
Enfoque: la idea es utilizar el método transversal de búsqueda en profundidad primero para realizar un seguimiento de todos los componentes conectados. Se utiliza una variable temporal para sumar todos los valores de los valores individuales de las strings conectadas. En cada recorrido de un componente conectado, el valor más pesado hasta ahora se compara con el valor actual y se actualiza en consecuencia. Después de que se hayan atravesado todos los componentes conectados, el máximo entre todos será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad temporal : O(E + V)
Espacio auxiliar: O(E + V)
Publicación traducida automáticamente
Artículo escrito por PratikBasu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA