Минимальное расстояние для посещения всех узлов неориентированного взвешенного дерева

Опубликовано: 12 Января, 2022

Дано взвешенное дерево с N узлами, начиная с 1 до N. Расстояние между любыми двумя узлами определяется весом ребра. Узел 1 является источником, задача - посетить все узлы дерева с минимальным пройденным расстоянием.

Примеры:

Input:
u[] = {1, 1, 2, 2, 1}
v[] = {2, 3, 5, 6, 4}
w[] = {1, 4, 2, 50, 5}
Output: 73
Input:
u[] = {1, 2}
v[] = {2, 3}
w[] = {3, 1}
Output: 4

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Предположим, что имеется n листов l ₁ , l ₂ , l ₃ , ……, l _n, а стоимость пути от корня до каждого листа равна c ₁ , c ₂ , c ₃ , ……, c _n .
Для перехода от l ₁ к l ₂ некоторые ребра будут посещены дважды (до LCA l ₁ и l ₂ все ребра будут посещены дважды), для l ₂ - l ₃ будут посещены некоторые из ребер ( до LCA l ₂ и l ₃ все ребра будут посещены дважды) дважды, и аналогично каждое ребро дерева будет посещено дважды (наблюдение).

Чтобы минимизировать затраты на перемещение, следует избегать пути максимальной стоимости от корня до некоторого листа.
Следовательно, стоимость = ( c ₁ + c ₂ + c ₃ + …… + c _n ) - max ( c ₁ , c ₂ , c ₃ , ……, c _n )
минимальная стоимость = (2 * сумма веса ребер) - max ( c ₁ , c ₂ , c ₃ , ……, c _n )
DFS можно использовать с некоторыми модификациями, чтобы найти наибольшее расстояние.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
class Edge{
     
    public:
     
    // from - The source of an edge
    // to - destination of an edge
    // wt - distance between two nodes
    int from;
    int to;
    long wt;
 
    Edge(int a, int b, long w)
    {
        from = a;
        to = b;
        wt = w;
    }
};
 
// Method to add an edge between two nodes
void add_edge(vector<vector<Edge>> &adj_lis,
              int to, int from, long wt)
{
    adj_lis[from].push_back(Edge(from, to, wt));
    adj_lis[to].push_back(Edge(to, from, wt));
}
 
// DFS method to find distance
// between node 1 to other nodes
void dfs(vector<vector<Edge>> &adj_lis,
         long val[], int v, int par,
         long sum, bool visited[])
{
    val[v] = sum;
    visited[v] = true;
     
    for(Edge e : adj_lis[v])
    {
        if (!visited[e.to])
            dfs(adj_lis, val, e.to,
                v, sum + e.wt, visited);
    }
}
 
// Driver code
int main()
{
     
    // Number of nodes
    // V - Total number of
    // nodes in a tree
    int v = 6;
     
    // adj_lis - It is used to
    // make the adjacency list of a tree
    vector<vector<Edge>> adj_lis(v);
     
    // val - This array stores the
    // distance from node 1 to node "n"
    long val[v];
     
    bool visited[v];
     
    int sum = 0;
     
    // Edge from a node to another
    // node with some weight
    int from[] = { 2, 3, 5, 6, 4 };
    int to[] = { 1, 1, 2, 2, 1 };
    int wt[] = { 1, 4, 2, 50, 5 };
     
    for(int i = 0; i < v - 1; i++)
    {
        sum += 2 * wt[i];
        add_edge(adj_lis, to[i] - 1,
                 from[i] - 1, wt[i]);
    }
     
    dfs(adj_lis, val, 0, -1, 0, visited);
    long large = INT_MIN;
     
    // Loop to find largest
    // distance in a val.
    int size = sizeof(val) / sizeof(long);
     
    for(int i = 1; i < size; i++)
        if (val[i] > large)
            large = val[i];
     
    cout << (sum - large);
}
 
// This code is contributed by sanjeev2552

Java

// Java implementation of the approach
import java.util.LinkedList;
import java.util.Scanner;
 
class Graph {
 
    class Edge {
 
        // from - The source of an edge
        // to - destination of an edge
        // wt - distance between two nodes
        int from;
        int to;
        long wt;
        Edge(int a, int b, long w)
        {
            from = a;
            to = b;
            wt = w;
        }
    }
 
    // adj_lis - It is used to
    // make the adjacency list of a tree
 
    // V - Total number of nodes in a tree
 
    // val - This array stores the
    // distance from node 1 to node "n"
    static LinkedList<Edge>[] adj_lis;
    static int V;
    static long val[];
 
    Graph(int v)
    {
        this.V = v;
        adj_lis = new LinkedList[V];
        for (int i = 0; i < V; i++)
            adj_lis[i] = new LinkedList<>();
    }
 
    // Method to add an edge between two nodes
    void add_edge(int to, int from, long wt)
    {
        adj_lis[from].add(
            new Edge(from, to, wt));
        adj_lis[to].add(
            new Edge(to, from, wt));
    }
 
    // DFS method to find distance
    // between node 1 to other nodes
    void dfs(int v,
             int par,
             long sum,
             boolean[] visited)
    {
        val[v] = sum;
        visited[v] = true;
        for (Edge e : adj_lis[v]) {
            if (!visited[e.to])
                dfs(e.to,
                    v,
                    sum + e.wt,
                    visited);
        }
    }
 
    // Driver code
    public static void main(String a[])
    {
 
        // Number of nodes
        int v = 6;
        Graph obj = new Graph(v);
        val = new long[v];
        boolean[] visited
            = new boolean[v];
 
        int sum = 0;
 
        // Edge from a node to another
        // node with some weight
        int from[] = { 2, 3, 5, 6, 4 };
        int to[] = { 1, 1, 2, 2, 1 };
        int wt[] = { 1, 4, 2, 50, 5 };
 
        for (int i = 0; i < v - 1; i++) {
            sum += 2 * wt[i];
            obj.add_edge(to[i] - 1,
                         from[i] - 1,
                         wt[i]);
        }
 
        obj.dfs(0, -1, 0, visited);
        long large = Integer.MIN_VALUE;
 
        // Loop to find largest
        // distance in a val.
        for (int i = 1; i < val.length;
             i++)
            if (val[i] > large)
                large = val[i];
 
        System.out.println(sum - large);
    }
}

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
class Graph
{
    public class Edge
    {
 
        // from - The source of an edge
        // to - destination of an edge
        // wt - distance between two nodes
        public int from;
        public int to;
        public long wt;
        public Edge(int a, int b, long w)
        {
            from = a;
            to = b;
            wt = w;
        }
    }
 
    // adj_lis - It is used to
    // make the adjacency list of a tree
 
    // V - Total number of nodes in a tree
 
    // val - This array stores the
    // distance from node 1 to node "n"
    public static List<Edge>[] adj_lis;
    public static int V;
    public static long []val;
 
    public Graph(int v)
    {
        V = v;
        adj_lis = new List<Edge>[V];
        for (int i = 0; i < V; i++)
            adj_lis[i] = new List<Edge>();
    }
 
    // Method to add an edge between two nodes
    void add_edge(int to, int from, long wt)
    {
        adj_lis[from].Add(
                 new Edge(from, to, wt));
        adj_lis[to].Add(
               new Edge(to, from, wt));
    }
 
    // DFS method to find distance
    // between node 1 to other nodes
    void dfs(int v,
            int par,
            long sum,
            bool[] visited)
    {
        val[v] = sum;
        visited[v] = true;
        foreach (Edge e in adj_lis[v])
        {
            if (!visited[e.to])
                dfs(e.to, v,
                    sum + e.wt, visited);
        }
    }
 
    // Driver code
    public static void Main(String []a)
    {
 
        // Number of nodes
        int v = 6;
        Graph obj = new Graph(v);
        val = new long[v];
        bool []visited = new bool[v];
 
        int sum = 0;
 
        // Edge from a node to another
        // node with some weight
        int []from = { 2, 3, 5, 6, 4 };
        int []to = { 1, 1, 2, 2, 1 };
        int []wt = { 1, 4, 2, 50, 5 };
 
        for (int i = 0; i < v - 1; i++)
        {
            sum += 2 * wt[i];
            obj.add_edge(to[i] - 1,
                       from[i] - 1, wt[i]);
        }
 
        obj.dfs(0, -1, 0, visited);
        long large = int.MinValue;
 
        // Loop to find largest
        // distance in a val.
        for (int i = 1; i < val.Length;
            i++)
            if (val[i] > large)
                large = val[i];
 
        Console.WriteLine(sum - large);
    }
}
 
// This code is contributed by Princi Singh

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Минимальное расстояние для посещения всех узлов неориентированного взвешенного дерева

C++

Java

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ