Рубрики

Минимальное связующее дерево продукта

Для связного и ненаправленного графа остовное дерево этого графа является подграфом, который является деревом и соединяет все вершины вместе. В одном графе может быть много разных связующих деревьев. Минимальное связующее дерево продуктов для взвешенного, связного и ненаправленного графа — это связующее дерево с весовым произведением, меньшим или равным весовому произведению любого другого связующего дерева. Весовое произведение связующего дерева — это произведение весов, соответствующих каждому ребру связующего дерева. Все веса данного графа будут положительными для простоты.

Примеры:



Minimum Product that we can obtain is 
180 for above graph by choosing edges 
0-1, 1-2, 0-3 and 1-4

Эта проблема может быть решена с помощью стандартных алгоритмов минимального связующего дерева, таких как krushkal и prim , но нам нужно изменить наш граф, чтобы использовать эти алгоритмы. Алгоритмы минимального связующего дерева пытаются минимизировать общую сумму весов, здесь нам нужно минимизировать общее произведение весов. Мы можем использовать свойство логарифмов, чтобы преодолеть эту проблему.
Как мы знаем,

  log(w1* w2 * w3 * …. * wN) = 
     log(w1) + log(w2) + log(w3) ….. + log(wN)  

Мы можем заменить каждый вес графа его логарифмическим значением, затем применим любой алгоритм минимального связующего дерева, который попытается минимизировать сумму логарифмов (wi), что, в свою очередь, минимизирует весовой продукт.
Например, график, шаги показаны на диаграмме ниже,


В приведенном ниже коде сначала мы построили лог-граф из заданного входного графа, затем этот граф задается в качестве входных данных для алгоритма MST prim, который минимизирует общую сумму весов дерева. Поскольку вес модифицированного графа является логарифмом фактического входного графа, мы фактически минимизируем произведение весов остовного дерева.

C ++

// AC / C ++ программа для получения минимального продукта
// связующее дерево Программа для матрицы смежности
// представление графика
#include <bits/stdc++.h>

  
// Количество вершин в графе
#define V 5

  
// Полезная функция для поиска вершины с минимумом
// значение ключа из набора еще не включенных вершин
// в MST

int minKey(int key[], bool mstSet[])

{

    // Инициализируем минимальное значение

    int min = INT_MAX, min_index;

  

    for (int v = 0; v < V; v++)

        if (mstSet[v] == false && key[v] < min)

            min = key[v], min_index = v;

  

    return min_index;

}

  
// Вспомогательная функция для печати построенного MST
// сохраняется в parent [] и печатает Minimum Obtaiable
// продукт

int printMST(int parent[], int n, int graph[V][V])

{

    printf("Edge   Weight\n");

    int minProduct = 1;

    for (int i = 1; i < V; i++) {

        printf("%d - %d    %d \n",

               parent[i], i, graph[i][parent[i]]);

  

        minProduct *= graph[i][parent[i]];

    }

    printf("Minimum Obtainable product is %d\n",

           minProduct);

}

  
// Функция для построения и печати MST для графа
// представлено с использованием представления матрицы смежности
// inputGraph отправляется для печати реальных ребер и
// logGraph отправляется для реальных операций MST

void primMST(int inputGraph[V][V], double logGraph[V][V])

{

    int parent[V]; // Массив для хранения построенного MST

    int key[V]; // Ключевые значения, используемые для выбора минимума

    // край веса в разрезе

    bool mstSet[V]; // Представлять множество вершин не

    // еще включены в MST

  

    // Инициализируем все ключи как бесконечные

    for (int i = 0; i < V; i++)

        key[i] = INT_MAX, mstSet[i] = false;

  

    // Всегда включать первую 1-ю вершину в MST.

    key[0] = 0; // Сделать ключ 0 так, чтобы эта вершина была

    // выбран в качестве первой вершины

    parent[0] = -1; // Первый узел всегда является корнем MST

  

    // MST будет иметь V вершин

    for (int count = 0; count < V - 1; count++) {

        // Выбрать минимальную ключевую вершину из набора

        // вершины еще не включены в MST

        int u = minKey(key, mstSet);

  

        // Добавить выбранную вершину в набор MST

        mstSet[u] = true;

  

        // Обновляем значение ключа и родительский индекс

        // смежные вершины выбранной вершины.

        // Рассмотрим только те вершины, которые еще не

        // включено в MST

        for (int v = 0; v < V; v++)

  

            // logGraph [u] [v] отличен от нуля только для

            // смежные вершины m mstSet [v] false

            // для вершин, еще не включенных в MST

            // Обновляем ключ только если logGraph [u] [v]

            // меньше ключа [v]

            if (logGraph[u][v] > 0 && mstSet[v] == false && logGraph[u][v] < key[v])

  

                parent[v] = u, key[v] = logGraph[u][v];

    }

  

    // выводим построенное MST

    printMST(parent, V, inputGraph);

}

  
// Метод получения минимального остовного дерева продукта

void minimumProductMST(int graph[V][V])

{

    double logGraph[V][V];

  

    // Создание logGraph из исходного графа

    for (int i = 0; i < V; i++) {

        for (int j = 0; j < V; j++) {

            if (graph[i][j] > 0)

                logGraph[i][j] = log(graph[i][j]);

            else

                logGraph[i][j] = 0;

        }

    }

  

    // Применяем стандартный алгоритм MST Прима на

    // Лог-график.

    primMST(graph, logGraph);

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Давайте создадим следующий график

           2 3

       (0) - (1) - (2)

        | / / |

       6 | 8 / / 5 | 7

        | / / |

       (3) ------- (4)

             9 * /

    int graph[V][V] = {

        { 0, 2, 0, 6, 0 },

        { 2, 0, 3, 8, 5 },

        { 0, 3, 0, 0, 7 },

        { 6, 8, 0, 0, 9 },

        { 0, 5, 7, 9, 0 },

    };

  

    // Распечатать решение

    minimumProductMST(graph);

  

    return 0;

}

Джава

// Java-программа для получения минимального продукта
// связующее дерево Программа для матрицы смежности
// представление графика

import java.util.*;

  

class GFG {

  

    // Количество вершин в графе

    static int V = 5;

  

    // Полезная функция для поиска вершины с минимумом

    // значение ключа из набора еще не включенных вершин

    // в MST

    static int minKey(int key[], boolean[] mstSet)

    {

        // Инициализируем минимальное значение

        int min = Integer.MAX_VALUE, min_index = 0;

  

        for (int v = 0; v < V; v++) {

            if (mstSet[v] == false && key[v] < min) {

                min = key[v];

                min_index = v;

            }

        }

        return min_index;

    }

  

    // Вспомогательная функция для печати построенного MST

    // сохраняется в parent [] и печатает Minimum Obtaiable

    // продукт

    static void printMST(int parent[], int n, int graph[][])

    {

        System.out.printf("Edge Weight\n");

        int minProduct = 1;

        for (int i = 1; i < V; i++) {

            System.out.printf("%d - %d %d \n",

                              parent[i], i, graph[i][parent[i]]);

  

            minProduct *= graph[i][parent[i]];

        }

        System.out.printf("Minimum Obtainable product is %d\n",

                          minProduct);

    }

  

    // Функция для построения и печати MST для графа

    // представлено с использованием представления матрицы смежности

    // inputGraph отправляется для печати реальных ребер и

    // logGraph отправляется для реальных операций MST

    static void primMST(int inputGraph[][], double logGraph[][])

    {

        int[] parent = new int[V]; // Массив для хранения построенного MST

        int[] key = new int[V]; // Ключевые значения, используемые для выбора минимума

        // край веса в разрезе

        boolean[] mstSet = new boolean[V]; // Представлять множество вершин не

        // еще включены в MST

  

        // Инициализируем все ключи как бесконечные

        for (int i = 0; i < V; i++) {

            key[i] = Integer.MAX_VALUE;

            mstSet[i] = false;

        }

        // Всегда включать первую 1-ю вершину в MST.

        key[0] = 0; // Сделать ключ 0 так, чтобы эта вершина была

        // выбран в качестве первой вершины

        parent[0] = -1; // Первый узел всегда является корнем MST

  

        // MST будет иметь V вершин

        for (int count = 0; count < V - 1; count++) {

            // Выбрать минимальную ключевую вершину из набора

            // вершины еще не включены в MST

            int u = minKey(key, mstSet);

  

            // Добавить выбранную вершину в набор MST

            mstSet[u] = true;

  

            // Обновляем значение ключа и родительский индекс

            // смежные вершины выбранной вершины.

            // Рассмотрим только те вершины, которые еще не

            // включено в MST

            for (int v = 0; v < V; v++) // logGraph [u] [v] отличен от нуля только для

            // смежные вершины m mstSet [v] false

            // для вершин, еще не включенных в MST

            // Обновляем ключ только если logGraph [u] [v]

            // меньше ключа [v]

            {

                if (logGraph[u][v] > 0

                    && mstSet[v] == false

                    && logGraph[u][v] < key[v]) {

  

                    parent[v] = u;

                    key[v] = (int)logGraph[u][v];

                }

            }

        }

  

        // выводим построенное MST

        printMST(parent, V, inputGraph);

    }

  

    // Метод получения минимального остовного дерева продукта

    static void minimumProductMST(int graph[][])

    {

        double[][] logGraph = new double[V][V];

  

        // Создание logGraph из исходного графа

        for (int i = 0; i < V; i++) {

            for (int j = 0; j < V; j++) {

                if (graph[i][j] > 0) {

                    logGraph[i][j] = Math.log(graph[i][j]);

                }

                else {

                    logGraph[i][j] = 0;

                }

            }

        }

  

        // Применяем стандартный алгоритм MST Прима на

        // Лог-график.

        primMST(graph, logGraph);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        / * Давайте создадим следующий график

        2 3

    (0) - (1) - (2)

        | / / |

    6 | 8 / / 5 | 7

        | / / |

    (3) ------- (4)

            9 * /

        int graph[][] = {

            { 0, 2, 0, 6, 0 },

            { 2, 0, 3, 8, 5 },

            { 0, 3, 0, 0, 7 },

            { 6, 8, 0, 0, 9 },

            { 0, 5, 7, 9, 0 },

        };

  

        // Распечатать решение

        minimumProductMST(graph);

    }

}

  
// Этот код предоставлен 29AjayKumar

C #

// C # программа для получения минимального продукта
// связующее дерево Программа для матрицы смежности
// представление графика

using System;

  

class GFG {

  

    // Количество вершин в графе

    static int V = 5;

  

    // Полезная функция для поиска вершины с минимумом

    // значение ключа из набора еще не включенных вершин

    // в MST

    static int minKey(int[] key, Boolean[] mstSet)

    {

        // Инициализируем минимальное значение

        int min = int.MaxValue, min_index = 0;

  

        for (int v = 0; v < V; v++) {

            if (mstSet[v] == false && key[v] < min) {

                min = key[v];

                min_index = v;

            }

        }

        return min_index;

    }

  

    // Вспомогательная функция для печати построенного MST

    // сохраняется в parent [] и печатает Minimum Obtaiable

    // продукт

    static void printMST(int[] parent, int n, int[, ] graph)

    {

        Console.Write("Edge Weight\n");

        int minProduct = 1;

        for (int i = 1; i < V; i++) {

            Console.Write("{0} - {1} {2} \n",

                          parent[i], i, graph[i, parent[i]]);

  

            minProduct *= graph[i, parent[i]];

        }

        Console.Write("Minimum Obtainable product is {0}\n",

                      minProduct);

    }

  

    // Функция для построения и печати MST для графа

    // представлено с использованием представления матрицы смежности

    // inputGraph отправляется для печати реальных ребер и

    // logGraph отправляется для реальных операций MST

    static void primMST(int[, ] inputGraph, double[, ] logGraph)

    {

        int[] parent = new int[V]; // Массив для хранения построенного MST

        int[] key = new int[V]; // Ключевые значения, используемые для выбора минимума

        // край веса в разрезе

        Boolean[] mstSet = new Boolean[V]; // Представлять множество вершин не

        // еще включены в MST

  

        // Инициализируем все ключи как бесконечные

        for (int i = 0; i < V; i++) {

            key[i] = int.MaxValue;

            mstSet[i] = false;

        }

        // Всегда включать первую 1-ю вершину в MST.

        key[0] = 0; // Сделать ключ 0 так, чтобы эта вершина была

        // выбран в качестве первой вершины

        parent[0] = -1; // Первый узел всегда является корнем MST

  

        // MST будет иметь V вершин

        for (int count = 0; count < V - 1; count++) {

            // Выбрать минимальную ключевую вершину из набора

            // вершины еще не включены в MST

            int u = minKey(key, mstSet);

  

            // Добавить выбранную вершину в набор MST

            mstSet[u] = true;

  

            // Обновляем значение ключа и родительский индекс

            // смежные вершины выбранной вершины.

            // Рассмотрим только те вершины, которые еще не

            // включено в MST

            for (int v = 0; v < V; v++) // logGraph [u, v] отличен от нуля только для

            // смежные вершины m mstSet [v] false

            // для вершин, еще не включенных в MST

            // Обновляем ключ, только если logGraph [u, v]

            // меньше ключа [v]

            {

                if (logGraph[u, v] > 0

                    && mstSet[v] == false

                    && logGraph[u, v] < key[v]) {

  

                    parent[v] = u;

                    key[v] = (int)logGraph[u, v];

                }

            }

        }

  

        // выводим построенное MST

        printMST(parent, V, inputGraph);

    }

  

    // Метод получения минимального остовного дерева продукта

    static void minimumProductMST(int[, ] graph)

    {

        double[, ] logGraph = new double[V, V];

  

        // Создание logGraph из исходного графа

        for (int i = 0; i < V; i++) {

            for (int j = 0; j < V; j++) {

                if (graph[i, j] > 0) {

                    logGraph[i, j] = Math.Log(graph[i, j]);

                }

                else {

                    logGraph[i, j] = 0;

                }

            }

        }

  

        // Применяем стандартный алгоритм MST Прима на

        // Лог-график.

        primMST(graph, logGraph);

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        / * Давайте создадим следующий график

        2 3

    (0) - (1) - (2)

        | / / |

    6 | 8 / / 5 | 7

        | / / |

    (3) ------- (4)

            9 * /

        int[, ] graph = {

            { 0, 2, 0, 6, 0 },

            { 2, 0, 3, 8, 5 },

            { 0, 3, 0, 0, 7 },

            { 6, 8, 0, 0, 9 },

            { 0, 5, 7, 9, 0 },

        };

  

        // Распечатать решение

        minimumProductMST(graph);

    }

}
/ * Этот код предоставлен PrinciRaj1992 * /



Выход:

Edge   Weight
0 - 1    2 
1 - 2    3 
0 - 3    6 
1 - 4    5 
Minimum Obtainable product is 180

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальное связующее дерево продукта

0.00 (0%) 0 votes