Suma máxima de valores de Nodes entre todos los componentes conectados de un gráfico no dirigido

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *