Рубрики

Алгоритм Прима с использованием priority_queue в STL

Для заданного ненаправленного связного и взвешенного графа найдите минимальное остовное дерево (MST) графа, используя алгоритм Прима.



Input : Adjacency List representation
        of above graph
Output :  Edges in MST
          0 - 1
          1 - 2
          2 - 3
          3 - 4
          2 - 5
          5 - 6
          6 - 7
          2 - 8


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

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

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

  • ExtractMin: из всех тех вершин, которые еще не были включены в MST, нам нужно получить вершину с минимальным значением ключа.
  • DecreaseKey: после извлечения вершины нам нужно обновить ключи смежных вершин, а если новый ключ меньше, обновить это в структуре данных.

Обсуждаемый здесь алгоритм может быть изменен так, что ключ уменьшения никогда не требуется. Идея состоит не в том, чтобы вставить все вершины в приоритетную очередь, а только те, которые не являются MST и были посещены через вершину, которая включена в MST. Мы отслеживаем вершины, включенные в MST, в отдельный логический массив в MST [].

1) Initialize keys of all vertices as infinite and 
   parent of every vertex as -1.

2) Create an empty priority_queue pq.  Every item
   of pq is a pair (weight, vertex). Weight (or 
   key) is used used as first item  of pair
   as first item is by default used to compare
   two pairs.

3) Initialize all vertices as not part of MST yet.
   We use boolean array inMST[] for this purpose.
   This array is required to make sure that an already
   considered vertex is not included in pq again. This
   is where Ptim's implementation differs from Dijkstra.
   In Dijkstr's algorithm, we didn't need this array as
   distances always increase. We require this array here 
   because key value of a processed vertex may decrease
   if not checked.

4) Insert source vertex into pq and make its key as 0.

5) While either pq doesn't become empty 
    a) Extract minimum key vertex from pq. 
       Let the extracted vertex be u.

    b) Include u in MST using inMST[u] = true.

    c) Loop through all adjacent of u and do 
       following for every vertex v.

           // If weight of edge (u,v) is smaller than
           // key of v and v is not already in MST
           If inMST[v] = false && key[v] > weight(u, v)

               (i) Update key of v, i.e., do
                     key[v] = weight(u, v)
               (ii) Insert v into the pq 
               (iv) parent[v] = u
               
6) Print MST edges using parent array.

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

// STL реализация алгоритма Прима для MST
#include<bits/stdc++.h>

using namespace std;

# define INF 0x3f3f3f3f

  
// iPair ==> Целочисленная пара

typedef pair<int, int> iPair;

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

class Graph

{

    int V;    // Количество вершин

  

    // В взвешенном графе нам нужно хранить вершину

    // и весовая пара для каждого ребра

    list< pair<int, int> > *adj;

  

public:

    Graph(int V);  // Конструктор

  

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

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

  

    // Распечатать MST используя алгоритм Прима

    void primMST();

};

  
// Распределяет память для списка смежности

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<iPair> [V];

}

  

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

{

    adj[u].push_back(make_pair(v, w));

    adj[v].push_back(make_pair(u, w));

}

  
// Печатает кратчайшие пути из src во все остальные вершины

void Graph::primMST()

{

    // Создать приоритетную очередь для хранения вершин, которые

    // преинмуссируются. Это странный синтаксис в C ++.

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

    // http://geeksquiz.com/implement-min-heap-using-stl/

    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

  

    int src = 0; // Взять вершину 0 в качестве источника

  

    // Создать вектор для ключей и инициализировать все

    // ключи как бесконечные (INF)

    vector<int> key(V, INF);

  

    // Хранить родительский массив, который в свою очередь хранит MST

    vector<int> parent(V, -1);

  

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

    vector<bool> inMST(V, false);

  

    // Вставить сам источник в приоритетную очередь и инициализировать

    // его ключ как 0.

    pq.push(make_pair(0, src));

    key[src] = 0;

  

    / * Цикл до тех пор, пока приоритетная очередь не станет пустой * /

    while (!pq.empty())

    {

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

        // вершина, извлечь ее из приоритетной очереди.

        // метка вершины хранится во второй из пары

        // нужно сделать так, чтобы сохранить вершины

        // отсортированный ключ (ключ должен быть первым элементом

        // в паре)

        int u = pq.top().second;

        pq.pop();

  

        inMST[u] = true// Включить вершину в MST

  

        // 'i' используется для получения всех смежных вершин вершины

        list< pair<int, int> >::iterator i;

        for (i = adj[u].begin(); i != adj[u].end(); ++i)

        {

            // Получить метку вершины и вес текущего смежного

            // из вас.

            int v = (*i).first;

            int weight = (*i).second;

  

            // Если v не в MST и вес (u, v) меньше

            // чем текущий ключ v

            if (inMST[v] == false && key[v] > weight)

            {

                // Обновление ключа v

                key[v] = weight;

                pq.push(make_pair(key[v], v));

                parent[v] = u;

            }

        }

    }

  

    // Печатать края MST используя родительский массив

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

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

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

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

    int V = 9;

    Graph g(V);

  

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

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

  

    g.primMST();

  

    return 0;

}

Временная сложность: O (E Log V))

Более быстрая реализация с использованием массива векторов представления взвешенного графа :

// STL реализация алгоритма Прима для MST
#include<bits/stdc++.h>

using namespace std;

# define INF 0x3f3f3f3f

  
// iPair ==> Целочисленная пара

typedef pair<int, int> iPair;

  
// Добавить ребро

void addEdge(vector <pair<int, int> > adj[], int u,

                                     int v, int wt)

{

    adj[u].push_back(make_pair(v, wt));

    adj[v].push_back(make_pair(u, wt));

}

  
// Печатает кратчайшие пути из src во все остальные вершины

void primMST(vector<pair<int,int> > adj[], int V)

{

    // Создать приоритетную очередь для хранения вершин, которые

    // преинмуссируются. Это странный синтаксис в C ++.

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

    // http://geeksquiz.com/implement-min-heap-using-stl/

    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

  

    int src = 0; // Взять вершину 0 в качестве источника

  

    // Создать вектор для ключей и инициализировать все

    // ключи как бесконечные (INF)

    vector<int> key(V, INF);

  

    // Хранить родительский массив, который в свою очередь хранит MST

    vector<int> parent(V, -1);

  

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

    vector<bool> inMST(V, false);

  

    // Вставить сам источник в приоритетную очередь и инициализировать

    // его ключ как 0.

    pq.push(make_pair(0, src));

    key[src] = 0;

  

    / * Цикл до тех пор, пока приоритетная очередь не станет пустой * /

    while (!pq.empty())

    {

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

        // вершина, извлечь ее из приоритетной очереди.

        // метка вершины хранится во второй из пары

        // нужно сделать так, чтобы сохранить вершины

        // отсортированный ключ (ключ должен быть первым элементом

        // в паре)

        int u = pq.top().second;

        pq.pop();

  

        inMST[u] = true; // Включить вершину в MST

  

        // Обходим все смежные с вами

        for (auto x : adj[u])

        {

            // Получить метку вершины и вес текущего смежного

            // из вас.

            int v = x.first;

            int weight = x.second;

  

            // Если v не в MST и вес (u, v) меньше

            // чем текущий ключ v

            if (inMST[v] == false && key[v] > weight)

            {

                // Обновление ключа v

                key[v] = weight;

                pq.push(make_pair(key[v], v));

                parent[v] = u;

            }

        }

    }

  

    // Печатать края MST используя родительский массив

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

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

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    int V = 9;

    vector<iPair > adj[V];

  

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

    addEdge(adj, 0, 1, 4);

    addEdge(adj, 0, 7, 8);

    addEdge(adj, 1, 2, 8);

    addEdge(adj, 1, 7, 11);

    addEdge(adj, 2, 3, 7);

    addEdge(adj, 2, 8, 2);

    addEdge(adj, 2, 5, 4);

    addEdge(adj, 3, 4, 9);

    addEdge(adj, 3, 5, 14);

    addEdge(adj, 4, 5, 10);

    addEdge(adj, 5, 6, 2);

    addEdge(adj, 6, 7, 1);

    addEdge(adj, 6, 8, 6);

    addEdge(adj, 7, 8, 7);

  

    primMST(adj, V);

  

    return 0;

}

Примечание. Как и в реализации приоритета Dijkstra , у нас может быть несколько записей для одной и той же вершины, поскольку мы не (и не можем) сделать isMST [v] = true в условии if.

// Если v не в MST и вес (u, v) меньше

 // чем текущий ключ v

 if (inMST[v] == false && key[v] > weight)

 {

      // Обновление ключа v

      key[v] = weight;

      pq.push(make_pair(key[v], v));

      parent[v] = u;

}

Но, как объяснено в алгоритме Дейкстры, временная сложность остается O (E Log V), поскольку в очереди приоритетов будет не более O (E) вершин, а O (Log E) будет таким же, как O (Log V).

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

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

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

Алгоритм Прима с использованием priority_queue в STL

0.00 (0%) 0 votes