Рубрики

Минимальное остовное дерево Прима (MST) | Жадный Алго-5

Графы, Жадный алгоритм

Мы обсудили алгоритм Крускала для минимального остовного дерева . Как и алгоритм Крускала, алгоритм Прима также является алгоритмом Жадности . Это начинается с пустого связующего дерева. Идея состоит в том, чтобы поддерживать два набора вершин. Первый набор содержит вершины, уже включенные в MST, другой набор содержит вершины, которые еще не включены. На каждом этапе он рассматривает все ребра, которые соединяют два набора, и выбирает ребро минимального веса из этих ребер. После выбора края он перемещает другую конечную точку края в набор, содержащий MST.
Группа ребер, которая соединяет два набора вершин в графе, называется разрезом в теории графов . Таким образом, на каждом шаге алгоритма Прима мы находим срез (из двух наборов, один содержит вершины, уже включенные в MST, а другой содержит остальные вершины), выбирает ребро минимального веса из среза и включает эту вершину в набор MST. (набор, который содержит уже включенные вершины).

Как работает алгоритм Prim? Идея алгоритма Прима проста: остовное дерево означает, что все вершины должны быть связаны. Таким образом, два непересекающихся подмножества (обсужденных выше) вершин должны быть соединены, чтобы составить остовное дерево. И они должны быть связаны с минимальным краем веса, чтобы сделать его минимальным остовным деревом.

Алгоритм
1) Создайте набор mstSet, который отслеживает вершины, уже включенные в MST.
2) Присвойте значение ключа всем вершинам входного графа. Инициализируйте все значения ключа как БЕСКОНЕЧНЫЙ. Присвойте ключу значение 0 для первой вершины, чтобы она была выбрана первой.
3) Хотя mstSet не включает в себя все вершины
…. a) Выберите вершину u, которой нет в mstSet и которая имеет минимальное значение ключа.
…. б) Включите u в mstSet.
…. c) Обновить значение ключа всех смежных вершин u . Чтобы обновить значения ключей, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v вес ребра uv меньше предыдущего значения ключа v , обновите значение ключа как вес uv

Давайте разберемся со следующим примером:

Набор mstSet изначально пуст, а ключи, назначенные вершинам: {0, INF, INF, INF, INF, INF, INF, INF, INF}, где INF указывает на бесконечность. Теперь выберите вершину с минимальным значением ключа. Вершина 0 выбрана, включите ее в mstSet . Таким образом, mstSet становится {0}. После включения в mstSet обновите значения ключей соседних вершин. Смежные вершины 0 равны 1 и 7. Значения ключей 1 и 7 обновляются как 4 и 8. В следующем подграфе показаны вершины и их ключевые значения, показаны только вершины с конечными значениями ключей. Вершины, включенные в MST, показаны зеленым цветом.

Выберите вершину с минимальным значением ключа и еще не включенную в MST (не в mstSET). Вершина 1 выбрана и добавлена в mstSet. Таким образом, mstSet теперь становится {0, 1}. Обновите значения ключей соседних вершин, равных 1. Значение ключа вершины 2 становится равным 8.

Выберите вершину с минимальным значением ключа и еще не включенную в MST (не в mstSET). Мы можем выбрать вершину 7 или вершину 2, пусть вершина 7 выбрана. Таким образом, mstSet теперь становится {0, 1, 7}. Обновите значения ключей смежных вершин 7. Значение ключа вершин 6 и 8 становится конечным (1 и 7 соответственно).

Выберите вершину с минимальным значением ключа и еще не включенную в MST (не в mstSET). Вершина 6 выбрана. Таким образом, mstSet теперь становится {0, 1, 7, 6}. Обновите значения ключей соседних вершин, равных 6. Значения ключей вершин 5 и 8 обновлены.

Мы повторяем вышеупомянутые шаги, пока mstSet не включает все вершины данного графа. Наконец, мы получаем следующий график.

Как реализовать описанный выше алгоритм?
Мы используем логический массив mstSet [] для представления набора вершин, включенных в MST. Если значение mstSet [v] равно true, то вершина v включается в MST, в противном случае нет. Ключ массива [] используется для хранения значений ключей всех вершин. Другой массив parent [] для хранения индексов родительских узлов в MST. Родительский массив — это выходной массив, который используется для отображения построенного MST.

C ++

// Программа на C ++ для Prim's Minimum
// Алгоритм связующего дерева (MST). Программа
// для отображения матрицы смежности графа
#include <bits/stdc++.h>

using namespace std;

  
// Количество вершин в графе
#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 []

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

{ 

    cout<<"Edge \tWeight\n"; 

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

        cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n"; 

} 

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

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

{ 

    // Массив для хранения построенного MST

    int parent[V]; 

      

    // Ключевые значения, используемые для выбора минимального веса края в разрезе

    int key[V]; 

      

    // Для представления набора вершин, еще не включенных в MST

    bool mstSet[V]; 

  

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

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

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

  

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

    // Сделать ключ 0 так, чтобы эта вершина была выбрана в качестве первой вершины.

    key[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++) 

  

            // graph [u] [v] отличен от нуля только для смежных вершин m

            // mstSet [v] false для вершин, еще не включенных в MST

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

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

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

    } 

  

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

    printMST(parent, graph); 

} 

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

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 } }; 

  

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

    primMST(graph); 

  

    return 0; 

} 

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

С

// AC программа для минимума Прима
// Алгоритм связующего дерева (MST). Программа
// для отображения матрицы смежности графа
#include <limits.h>
#include <stdbool.h>
#include <stdio.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 []

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

{

    printf("Edge \tWeight\n");

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

        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);

}

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

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

{

    // Массив для хранения построенного MST

    int parent[V];

    // Ключевые значения, используемые для выбора минимального веса края в разрезе

    int key[V];

    // Для представления набора вершин, еще не включенных в MST

    bool mstSet[V];

  

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

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

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

  

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

    // Сделать ключ 0 так, чтобы эта вершина была выбрана в качестве первой вершины.

    key[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++)

  

            // graph [u] [v] отличен от нуля только для смежных вершин m

            // mstSet [v] false для вершин, еще не включенных в MST

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

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

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

    }

  

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

    printMST(parent, graph);

}

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

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 } };

  

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

    primMST(graph);

  

    return 0;

}

Джава

// Java-программа для алгоритма Prim Minimum Spanning Tree (MST).
// Программа для представления графа в матрице смежности

  

import java.util.*;

import java.lang.*;

import java.io.*;

  

class MST {

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

    private static final int V = 5;

  

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

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

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

    {

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

        int min = Integer.MAX_VALUE, min_index = -1;

  

        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 []

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

    {

        System.out.println("Edge \tWeight");

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

            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);

    }

  

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

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

    void primMST(int graph[][])

    {

        // Массив для хранения построенного MST

        int parent[] = new int[V];

  

        // Ключевые значения, используемые для выбора минимального веса края в разрезе

        int key[] = new int[V];

  

        // Для представления набора вершин, еще не включенных в MST

        Boolean mstSet[] = new Boolean[V];

  

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

        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++)

  

                // graph [u] [v] отличен от нуля только для смежных вершин m

                // mstSet [v] false для вершин, еще не включенных в MST

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

                if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {

                    parent[v] = u;

                    key[v] = graph[u][v];

                }

        }

  

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

        printMST(parent, graph);

    }

  

    public static void main(String[] args)

    {

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

        2 3

        (0) - (1) - (2)

        | / / |

        6 | 8 / / 5 | 7

        | / / |

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

            9 * /

        MST t = new MST();

        int graph[][] = new int[][] { { 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 } };

  

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

        t.primMST(graph);

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Программа на Python для алгоритма Prim Minimum Spanning Tree (MST).
# Программа предназначена для представления матрицы графа смежности

  

import sys # Библиотека для INT_MAX

  

class Graph():

  

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)] 

                    for row in range(vertices)]

  

    # Утилита для печати созданного MST, хранящегося в parent []

    def printMST(self, parent):

        print "Edge \tWeight"

        for i in range(1, self.V):

            print parent[i], "-", i, "\t", self.graph[i][ parent[i] ]

  

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

    # минимальное значение расстояния от множества вершин

    # еще не включено в дерево кратчайших путей

    def minKey(self, key, mstSet):

  

        # Инициализировать минимальное значение

        min = sys.maxint

  

        for v in range(self.V):

            if key[v] < min and mstSet[v] == False:

                min = key[v]

                min_index = v

  

        return min_index

  

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

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

    def primMST(self):

  

        # Ключевые значения, используемые для выбора минимального веса края в разрезе

        key = [sys.maxint] * self.V

        parent = [None] * self.V # Массив для хранения построенного MST

        # Сделать ключ 0, чтобы эта вершина была выбрана в качестве первой вершины

        key[0] = 0 

        mstSet = [False] * self.V

  

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

  

        for cout in range(self.V):

  

            # Выберите минимальное расстояние от вершины до

            # множество вершин, еще не обработанных.

            # u всегда равен src в первой итерации

            u = self.minKey(key, mstSet)

  

            # Поместите вершину минимального расстояния в

            # дерево кратчайшего пути

            mstSet[u] = True

  

            # Обновить значение dist соседних вершин

            # выбранной вершины, только если текущий

            # расстояние больше нового расстояния и

            # вершина не в дереве кратчайшего пути

            for v in range(self.V):

                # graph [u] [v] отличен от нуля только для смежных вершин m

                # mstSet [v] имеет значение false для вершин, еще не включенных в MST

                # Обновлять ключ, только если график [u] [v] меньше, чем ключ [v]

                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:

                        key[v] = self.graph[u][v]

                        parent[v] = u

  

        self.printMST(parent)

  

g = Graph(5)

g.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]]

  
g.primMST();

  
# Предоставлено Дивьяншу Мехта

C #

// AC # программа для минимума Прима
// Алгоритм связующего дерева (MST).
// Программа для смежности
// матричное представление графика

using System;

class MST {

  

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

    static int V = 5;

  

    // Полезная функция для поиска

    // вершина с минимальным ключом

    // значение из множества вершин

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

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

    {

  

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

        int min = int.MaxValue, min_index = -1;

  

        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 []

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

    {

        Console.WriteLine("Edge \tWeight");

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

            Console.WriteLine(parent[i] + " - " + i + "\t" + graph[i, parent[i]]);

    }

  

    // Функция для построения и

    // выводим MST для представленного графика

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

    static void primMST(int[, ] graph)

    {

  

        // Массив для хранения построенного MST

        int[] parent = new int[V];

  

        // Ключевые значения, используемые для выбора

        // край минимального веса в разрезе

        int[] key = new int[V];

  

        // Представлять множество вершин

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

        bool[] mstSet = new bool[V];

  

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

        // как БЕСКОНЕЧНО

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

            key[i] = int.MaxValue;

            mstSet[i] = false;

        }

  

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

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

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

        // Первый узел всегда является корнем MST

        key[0] = 0;

        parent[0] = -1;

  

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

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

  

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

            // из множества вершин

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

            int u = minKey(key, mstSet);

  

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

            // в MST Set

            mstSet[u] = true;

  

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

            // индекс смежных вершин

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

            // только те вершины, которые

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

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

  

                // graph [u] [v] не только ноль

                // для смежных вершин m

                // mstSet [v] false для вершин

                // еще не включен в обновление MST

                // ключ, только если graph [u] [v]

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

                if (graph[u, v] != 0 && mstSet[v] == false

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

                    parent[v] = u;

                    key[v] = graph[u, v];

                }

        }

  

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

        printMST(parent, graph);

    }

  

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

    public static void Main()

    {

  

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

        2 3

        (0) - (1) - (2)

        | / / |

        6 | 8 / / 5 | 7

        | / / |

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

            9 * /

  

        int[, ] graph = new int[, ] { { 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 } };

  

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

        primMST(graph);

    }

}

  
// Этот код предоставлен anuj_67.


Выход:

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

Сложность времени указанной программы составляет O (V ^ 2). Если входной граф представлен с использованием списка смежности , то временная сложность алгоритма Прима может быть уменьшена до O (E log V) с помощью двоичной кучи. Пожалуйста, см. Prim's MST для представления списка смежности для более подробной информации.

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

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

Минимальное остовное дерево Прима (MST) | Жадный Алго-5

0.00 (0%) 0 votes