Рубрики

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

Для заданного ненаправленного связного и взвешенного графа найдите M inimum S панорамирования T ree (MST) графа, используя алгоритм Крускала.



Input :   Graph as an array of edges
Output :  Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

Note :  There are two possible MSTs, the other
        MST includes edge 1-2 in place of 0-7. 

Мы обсудили ниже реализации MST Крускала.

Жадные алгоритмы | Набор 2 (алгоритм минимального связующего дерева Крускала)

Ниже приведены шаги для нахождения MST с использованием алгоритма Крускала

  1. Сортируйте все ребра в порядке убывания их веса.
  2. Выберите самый маленький край. Проверьте, образует ли он цикл с сформированным до сих пор остовным деревом. Если цикл не сформирован, включите это ребро. Иначе, откажитесь от этого.
  3. Повторяйте шаг № 2, пока в связующем дереве не появятся ребра (V-1).

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

  1. Используйте вектор ребер, который состоит из всех ребер в графе, и каждый элемент вектора будет содержать 3 параметра: источник, пункт назначения и стоимость ребра между источником и пунктом назначения.
    		vector<pair<int, pair<int, int> > > edges;

    Здесь во внешней паре (т. Е. Pair <int, pair <int, int>>) первый элемент соответствует стоимости ребра, в то время как второй элемент сам является парой и содержит две вершины ребра.

  2. Используйте встроенный std :: sort для сортировки ребер в неубывающем порядке; по умолчанию функция сортировки сортируется в неубывающем порядке.
  3. Мы используем алгоритм поиска объединения, чтобы проверить, образует ли его текущее ребро цикл, если он добавлен в текущий MST. Если да, откажитесь, включите его (союз).

Псевдокод:

// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
	parent[v] = v;
	rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)

Ниже приведена реализация вышеуказанного алгоритма на C ++.

// C ++ программа для алгоритма Крускала для поиска минимума
// остовное дерево данного связанного, ненаправленного и
// взвешенный график
#include<bits/stdc++.h>

using namespace std;

  
// Создание ярлыка для целой пары

typedef  pair<int, int> iPair;

  
// Структура для представления графика

struct Graph

{

    int V, E;

    vector< pair<int, iPair> > edges;

  

    // Конструктор

    Graph(int V, int E)

    {

        this->V = V;

        this->E = E;

    }

  

    // Сервисная функция для добавления ребра

    void addEdge(int u, int v, int w)

    {

        edges.push_back({w, {u, v}});

    }

  

    // Функция для поиска MST с использованием Kruskal's

    // алгоритм MST

    int kruskalMST();

};

  
// Для представления непересекающихся множеств

struct DisjointSets

{

    int *parent, *rnk;

    int n;

  

    // Конструктор.

    DisjointSets(int n)

    {

        // Распределить память

        this->n = n;

        parent = new int[n+1];

        rnk = new int[n+1];

  

        // Изначально все вершины находятся в

        // разные множества и имеют ранг 0.

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

        {

            rnk[i] = 0;

  

            // каждый элемент является родителем самого себя

            parent[i] = i;

        }

    }

  

    // Найти родителя узла 'u'

    // Сжатие пути

    int find(int u)

    {

        / * Сделать родителем узлов в пути

           от u -> parent [u] указывает на parent [u] * /

        if (u != parent[u])

            parent[u] = find(parent[u]);

        return parent[u];

    }

  

    // Союз по рангу

    void merge(int x, int y)

    {

        x = find(x), y = find(y);

  

        / * Сделать дерево с меньшей высотой

           поддерево другого дерева * /

        if (rnk[x] > rnk[y])

            parent[y] = x;

        else // Если rnk [x] <= rnk [y]

            parent[x] = y;

  

        if (rnk[x] == rnk[y])

            rnk[y]++;

    }

};

  

 / * Функции возвращают вес MST * / 

  

int Graph::kruskalMST()

{

    int mst_wt = 0; // Инициализировать результат

  

    // Сортировка ребер в порядке возрастания на основе стоимости

    sort(edges.begin(), edges.end());

  

    // Создать непересекающиеся множества

    DisjointSets ds(V);

  

    // Перебирать все отсортированные ребра

    vector< pair<int, iPair> >::iterator it;

    for (it=edges.begin(); it!=edges.end(); it++)

    {

        int u = it->second.first;

        int v = it->second.second;

  

        int set_u = ds.find(u);

        int set_v = ds.find(v);

  

        // Проверяем, создается ли выбранное ребро

        // цикл или нет (цикл создается, если вы

        // и v принадлежат одному и тому же набору)

        if (set_u != set_v)

        {

            // Текущее ребро будет в MST

            // так что распечатай

            cout << u << " - " << v << endl;

  

            // Обновление веса MST

            mst_wt += it->first;

  

            // Объединяем два набора

            ds.merge(set_u, set_v);

        }

    }

  

    return mst_wt;

}

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

int main()

{

    / * Давайте создадим показанный выше взвешенный

       и неотправленный граф * /

    int V = 9, E = 14;

    Graph g(V, E);

  

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

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

  

    cout << "Edges of MST are \n";

    int mst_wt = g.kruskalMST();

  

    cout << "\nWeight of MST is " << mst_wt;

  

    return 0;

}

Выход :

 Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

Оптимизация:
Приведенный выше код может быть оптимизирован для остановки основного цикла Kruskal, когда число выбранных ребер становится V-1. Мы знаем, что MST имеет ребра V-1, и нет смысла повторяться после выбора ребер V-1. Мы не добавили эту оптимизацию, чтобы сделать код простым.

Ссылки:
Введение в алгоритмы Кормена Лизерсона Ривеста и Стейна (CLRS) 3

Сложность времени и пошаговая иллюстрация обсуждаются в предыдущем посте об алгоритме Крускала.

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

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

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

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

0.00 (0%) 0 votes