Рубрики

Prim's MST для представления списка смежности | Жадный Алго-6

Мы рекомендуем прочитать следующие два сообщения в качестве предпосылки этого сообщения.

1. Жадные алгоритмы | Комплект 5 (Минимальное остовное дерево Прима (MST))
2. Граф и его представления

Мы обсудили алгоритм Прима и его реализацию для представления графа в матрице смежности . Временная сложность для матричного представления составляет O (V ^ 2). В этом посте обсуждается алгоритм O (ELogV) для представления списка смежности.
Как обсуждалось в предыдущем посте, в алгоритме Прима поддерживаются два набора, один набор содержит список вершин, уже включенных в MST, другой набор содержит еще не включенные вершины. С представлением списка смежности все вершины графа могут быть пройдены за O (V + E) время с использованием BFS . Идея состоит в том, чтобы обойти все вершины графа, используя BFS, и использовать Min Heap для хранения вершин, еще не включенных в MST. Min Heap используется в качестве приоритетной очереди, чтобы получить минимальный край веса от среза . Min Heap используется в качестве временной сложности операций, таких как извлечение минимального элемента и уменьшение значения ключа O (LogV) в Min Heap.

Ниже приведены подробные шаги.
1) Создайте Min Heap размера V, где V — количество вершин в данном графе. Каждый узел min heap содержит номер вершины и ключевое значение вершины.
2) Инициализируйте Min Heap с первой вершиной в качестве корня (значение ключа, назначенное первой вершине, равно 0). Значение ключа, присвоенное всем остальным вершинам, равно INF (бесконечно).
3) Пока Min Heap не пусто, сделайте следующее
… .. a) Извлечь узел минимального значения из Min Heap. Пусть извлеченная вершина будет u.
… .. b) Для каждой смежной вершины v из u проверьте, находится ли v в Min Heap (еще не включено в MST). Если v находится в Min Heap и его значение ключа больше, чем вес uv, то обновите значение ключа v как вес uv.

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

Первоначально значение ключа первой вершины равно 0 и INF (бесконечно) для всех остальных вершин. Таким образом, вершина 0 извлекается из Min Heap, а ключевые значения вершин, смежных с 0 (1 и 7), обновляются. Min Heap содержит все вершины, кроме вершины 0.
Вершины зеленого цвета — это вершины, включенные в MST.

Поскольку значение ключа вершины 1 является минимальным среди всех узлов в Min Heap, оно извлекается из Min Heap, а значения ключа для вершин, смежных с 1, обновляются (Key обновляется, если вершина не находится в Min Heap, а предыдущее значение ключа больше чем вес ребра от 1 до соседнего). Min Heap содержит все вершины, кроме вершин 0 и 1.

Поскольку значение ключа вершины 7 является минимальным среди всех узлов в Min Heap, оно извлекается из Min Heap, а значения ключа для вершин, смежных с 7, обновляются (Key обновляется, если вершина не находится в Min Heap, а предыдущее значение ключа больше чем вес ребра от 7 до соседних). Min Heap содержит все вершины, кроме вершин 0, 1 и 7.

Поскольку значение ключа вершины 6 является минимальным среди всех узлов в Min Heap, оно извлекается из Min Heap, а значения ключа для вершин, смежных с 6, обновляются (Key обновляется, если вершина не находится в Min Heap, а предыдущее значение ключа больше чем вес ребра от 6 до соседних). Min Heap содержит все вершины, кроме вершин 0, 1, 7 и 6.

Вышеуказанные шаги повторяются для остальных узлов в Min Heap, пока Min Heap не станет пустым

C ++

// C / C ++ программа для Prim's MST для представления графа в списке смежности

  
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

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

struct AdjListNode {

    int dest;

    int weight;

    struct AdjListNode* next;

};

  
// Структура для представления списка смежности

struct AdjList {

    struct AdjListNode* head; // указатель на головной узел списка

};

  
// Структура для представления графа. Граф - это массив списков смежности.
// Размер массива будет V (количество вершин в графе)

struct Graph {

    int V;

    struct AdjList* array;

};

  
// Служебная функция для создания нового узла списка смежности

struct AdjListNode* newAdjListNode(int dest, int weight)

{

    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));

    newNode->dest = dest;

    newNode->weight = weight;

    newNode->next = NULL;

    return newNode;

}

  
// Вспомогательная функция, которая создает граф из V вершин

struct Graph* createGraph(int V)

{

    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

    graph->V = V;

  

    // Создать массив списков смежности. Размер массива будет V

    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

  

    // Инициализируем каждый список смежности как пустой, сделав head как NULL

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

        graph->array[i].head = NULL;

  

    return graph;

}

  
// Добавляем ребро в неориентированный граф

void addEdge(struct Graph* graph, int src, int dest, int weight)

{

    // Добавить ребро из src в dest. Новый узел добавляется в смежность

    // список источников Узел добавлен в начале

    struct AdjListNode* newNode = newAdjListNode(dest, weight);

    newNode->next = graph->array[src].head;

    graph->array[src].head = newNode;

  

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

    newNode = newAdjListNode(src, weight);

    newNode->next = graph->array[dest].head;

    graph->array[dest].head = newNode;

}

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

struct MinHeapNode {

    int v;

    int key;

};

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

struct MinHeap {

    int size; // Количество узлов кучи, присутствующих в данный момент

    int capacity; // Емкость мин кучи

    int* pos; // Это необходимо для lowerKey ()

    struct MinHeapNode** array;

};

  
// Вспомогательная функция для создания нового узла Min Heap

struct MinHeapNode* newMinHeapNode(int v, int key)

{

    struct MinHeapNode* minHeapNode = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));

    minHeapNode->v = v;

    minHeapNode->key = key;

    return minHeapNode;

}

  
// Утилита для создания Min Heap

struct MinHeap* createMinHeap(int capacity)

{

    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));

    minHeap->pos = (int*)malloc(capacity * sizeof(int));

    minHeap->size = 0;

    minHeap->capacity = capacity;

    minHeap->array = (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*));

    return minHeap;

}

  
// Вспомогательная функция для замены двух узлов минимальной кучи. Требуется в течение минуты heapify

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)

{

    struct MinHeapNode* t = *a;

    *a = *b;

    *b = t;

}

  
// Стандартная функция для работы с данным idx
// Эта функция также обновляет положение узлов, когда они меняются местами.
// Позиция нужна для lowerKey ()

void minHeapify(struct MinHeap* minHeap, int idx)

{

    int smallest, left, right;

    smallest = idx;

    left = 2 * idx + 1;

    right = 2 * idx + 2;

  

    if (left < minHeap->size && minHeap->array[left]->key < minHeap->array[smallest]->key)

        smallest = left;

  

    if (right < minHeap->size && minHeap->array[right]->key < minHeap->array[smallest]->key)

        smallest = right;

  

    if (smallest != idx) {

        // Узлы, которые нужно поменять местами в минимальной куче

        MinHeapNode* smallestNode = minHeap->array[smallest];

        MinHeapNode* idxNode = minHeap->array[idx];

  

        // Меняем местами

        minHeap->pos[smallestNode->v] = idx;

        minHeap->pos[idxNode->v] = smallest;

  

        // Переставляем узлы

        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);

  

        minHeapify(minHeap, smallest);

    }

}

  
// Утилита для проверки, является ли данный minHeap пустым или нет

int isEmpty(struct MinHeap* minHeap)

{

    return minHeap->size == 0;

}

  
// Стандартная функция для извлечения минимального узла из кучи

struct MinHeapNode* extractMin(struct MinHeap* minHeap)

{

    if (isEmpty(minHeap))

        return NULL;

  

    // Сохраняем корневой узел

    struct MinHeapNode* root = minHeap->array[0];

  

    // Заменить корневой узел последним узлом

    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];

    minHeap->array[0] = lastNode;

  

    // Обновляем позицию последнего узла

    minHeap->pos[root->v] = minHeap->size - 1;

    minHeap->pos[lastNode->v] = 0;

  

    // Уменьшаем размер кучи и корнем корнем

    --minHeap->size;

    minHeapify(minHeap, 0);

  

    return root;

}

  
// Функция для уменьшения значения ключа данной вершины v. Эта функция
// использует pos [] из min heap, чтобы получить текущий индекс узла в min heap

void decreaseKey(struct MinHeap* minHeap, int v, int key)

{

    // Получить индекс v в массиве кучи

    int i = minHeap->pos[v];

  

    // Получить узел и обновить его значение ключа

    minHeap->array[i]->key = key;

  

    // Подниматься вверх, пока целое дерево не печетно.

    // Это цикл O (Logn)

    while (i && minHeap->array[i]->key < minHeap->array[(i - 1) / 2]->key) {

        // Поменяем местами этот узел

        minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;

        minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;

        swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);

  

        // перейти к родительскому индексу

        i = (i - 1) / 2;

    }

}

  
// Полезная функция, чтобы проверить, является ли данная вершина
// 'v' в минимальной куче или нет

bool isInMinHeap(struct MinHeap* minHeap, int v)

{

    if (minHeap->pos[v] < minHeap->size)

        return true;

    return false;

}

  
// Утилита, используемая для печати построенного MST

void printArr(int arr[], int n)

{

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

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

}

  
// Основная функция, которая создает минимальное связующее дерево (MST)
// используя алгоритм Прима

void PrimMST(struct Graph* graph)

{

    int V = graph->V; // Получить количество вершин в графе

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

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

  

    // minHeap представляет множество E

    struct MinHeap* minHeap = createMinHeap(V);

  

    // Инициализируем минимальную кучу со всеми вершинами. Ключевое значение

    // все вершины (кроме 0-й вершины) изначально бесконечны

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

        parent[v] = -1;

        key[v] = INT_MAX;

        minHeap->array[v] = newMinHeapNode(v, key[v]);

        minHeap->pos[v] = v;

    }

  

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

    // извлекается первым

    key[0] = 0;

    minHeap->array[0] = newMinHeapNode(0, key[0]);

    minHeap->pos[0] = 0;

  

    // изначально размер min heap равен V

    minHeap->size = V;

  

    // В цикле followin min heap содержит все узлы

    // еще не добавлено в MST.

    while (!isEmpty(minHeap)) {

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

        struct MinHeapNode* minHeapNode = extractMin(minHeap);

        int u = minHeapNode->v; // Сохраняем извлеченный номер вершины

  

        // Обход всех смежных вершин u (извлеченный

        // вершина) и обновить их ключевые значения

        struct AdjListNode* pCrawl = graph->array[u].head;

        while (pCrawl != NULL) {

            int v = pCrawl->dest;

  

            // Если v еще не включено в MST и вес uv равен

            // меньше значения ключа v, затем обновляем значение ключа и

            // родитель v

            if (isInMinHeap(minHeap, v) && pCrawl->weight < key[v]) {

                key[v] = pCrawl->weight;

                parent[v] = u;

                decreaseKey(minHeap, v, key[v]);

            }

            pCrawl = pCrawl->next;

        }

    }

  

    // печатаем ребра MST

    printArr(parent, V);

}

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

int main()

{

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

    int V = 9;

    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1, 4);

    addEdge(graph, 0, 7, 8);

    addEdge(graph, 1, 2, 8);

    addEdge(graph, 1, 7, 11);

    addEdge(graph, 2, 3, 7);

    addEdge(graph, 2, 8, 2);

    addEdge(graph, 2, 5, 4);

    addEdge(graph, 3, 4, 9);

    addEdge(graph, 3, 5, 14);

    addEdge(graph, 4, 5, 10);

    addEdge(graph, 5, 6, 2);

    addEdge(graph, 6, 7, 1);

    addEdge(graph, 6, 8, 6);

    addEdge(graph, 7, 8, 7);

  

    PrimMST(graph);

  

    return 0;

}

Джава

// Java-программа для MST Prim для
// представление списка смежности графа

import java.util.LinkedList;

import java.util.TreeSet;

import java.util.Comparator;

  

public class prims {

    class node1 {

  

        // Сохраняет конечную вершину в списке смежности

        int dest;

  

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

        int weight;

  

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

        node1(int a, int b)

        {

            dest = a;

            weight = b;

        }

    }

    static class Graph {

  

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

        int V;

  

        // Список смежных узлов данной вершины

        LinkedList<node1>[] adj;

  

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

        Graph(int e)

        {

            V = e;

            adj = new LinkedList[V];

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

                adj[o] = new LinkedList<>();

        }

    }

  

    // класс для представления узла в PriorityQueue

    // Сохраняет вершину и соответствующую ей

    // значение ключа

    class node {

        int vertex;

        int key;

    }

  

    // Класс компаратора, созданный для PriorityQueue

    // возвращает 1, если node0.key> node1.key

    // возвращает 0, если node0.key <node1.key и

    // возвращает -1 в противном случае

    class comparator implements Comparator<node> {

  

        @Override

        public int compare(node node0, node node1)

        {

            return node0.key - node1.key;

        }

    }

  

    // метод для добавления ребра

    // между двумя вершинами

    void addEdge(Graph graph, int src, int dest, int weight)

    {

  

        node1 node0 = new node1(dest, weight);

        node1 node = new node1(src, weight);

        graph.adj[src].addLast(node0);

        graph.adj[dest].addLast(node);

    }

  

    // метод, используемый для поиска MST

    void prims_mst(Graph graph)

    {

  

        // находится ли вершина в PriorityQueue или нет

        Boolean[] mstset = new Boolean[graph.V];

        node[] e = new node[graph.V];

  

        // Хранит родителей вершины

        int[] parent = new int[graph.V];

  

        for (int o = 0; o < graph.V; o++)

            e[o] = new node();

  

        for (int o = 0; o < graph.V; o++) {

  

            // Инициализировать в false

            mstset[o] = false;

  

            // Инициализировать значения ключа в бесконечность

            e[o].key = Integer.MAX_VALUE;

            e[o].vertex = o;

            parent[o] = -1;

        }

  

        // Включить исходную вершину в mstset

        mstset[0] = true;

  

        // Установить значение ключа в 0

        // чтобы он был извлечен первым

        // вне PriorityQueue

        e[0].key = 0;

  

        // Используем TreeSet вместо PriorityQueue, так как функция удаления PQ - это O (n) в Java.

        TreeSet<node> queue = new TreeSet<node>(new comparator());

  

        for (int o = 0; o < graph.V; o++)

            queue.add(e[o]);

  

        // Циклы пока очередь не пуста

        while (!queue.isEmpty()) {

  

            // Извлекает узел со значением ключа min

            node node0 = queue.pollFirst();

  

            // Включить этот узел в mstset

            mstset[node0.vertex] = true;

  

            // Для всех смежных вершин извлеченной вершины V

            for (node1 iterator : graph.adj[node0.vertex]) {

  

                // Если V в очереди

                if (mstset[iterator.dest] == false) {

                    // Если значение ключа соседней вершины равно

                    // больше чем извлеченный ключ

                    // обновляем значение ключа соседней вершины

                    // обновить сначала удалить и добавить обновленную вершину

                    if (e[iterator.dest].key > iterator.weight) {

                        queue.remove(e[iterator.dest]);

                        e[iterator.dest].key = iterator.weight;

                        queue.add(e[iterator.dest]);

                        parent[iterator.dest] = node0.vertex;

                    }

                }

            }

        }

  

        // Печатает пару вершин mst

        for (int o = 1; o < graph.V; o++)

            System.out.println(parent[o] + " "

                               + "-"

                               + " " + o);

    }

  

    public static void main(String[] args)

    {

        int V = 9;

  

        Graph graph = new Graph(V);

  

        prims e = new prims();

  

        e.addEdge(graph, 0, 1, 4);

        e.addEdge(graph, 0, 7, 8);

        e.addEdge(graph, 1, 2, 8);

        e.addEdge(graph, 1, 7, 11);

        e.addEdge(graph, 2, 3, 7);

        e.addEdge(graph, 2, 8, 2);

        e.addEdge(graph, 2, 5, 4);

        e.addEdge(graph, 3, 4, 9);

        e.addEdge(graph, 3, 5, 14);

        e.addEdge(graph, 4, 5, 10);

        e.addEdge(graph, 5, 6, 2);

        e.addEdge(graph, 6, 7, 1);

        e.addEdge(graph, 6, 8, 6);

        e.addEdge(graph, 7, 8, 7);

  

        // Метод вызван

        e.prims_mst(graph);

    }

}
// Этот код предоставлен Викашем Кумаром Дубей

питон

# Программа Python для MST Prims для
# представление списка смежности графа

  

from collections import defaultdict

import sys

  

class Heap():

  

    def __init__(self):

        self.array = []

        self.size = 0

        self.pos = []

  

    def newMinHeapNode(self, v, dist):

        minHeapNode = [v, dist]

        return minHeapNode

  

    # Утилита для замены двух узлов

    # мин куча. Требуется в течение минуты heapify

    def swapMinHeapNode(self, a, b):

        t = self.array[a]

        self.array[a] = self.array[b]

        self.array[b] = t

  

    # Стандартная функция для кучи на заданном idx

    # Эта функция также обновляет положение узлов

    # когда они поменялись местами. Позиция нужна

    # для lowerKey ()

    def minHeapify(self, idx):

        smallest = idx

        left = 2 * idx + 1

        right = 2 * idx + 2

  

        if left < self.size and self.array[left][1] < \

                                self.array[smallest][1]:

            smallest = left

  

        if right < self.size and self.array[right][1] < \

                                self.array[smallest][1]:

            smallest = right

  

        # Узлы, которые нужно поменять местами в минимальной куче

        # если idx не самый маленький

        if smallest != idx:

  

            # Поменять позиции

            self.pos[ self.array[smallest][0] ] = idx

            self.pos[ self.array[idx][0] ] = smallest

  

            # Перестановка узлов

            self.swapMinHeapNode(smallest, idx)

  

            self.minHeapify(smallest)

  

    # Стандартная функция для извлечения минимального узла из кучи

    def extractMin(self):

  

        # Вернуть NULL, если куча пуста

        if self.isEmpty() == True:

            return

  

        # Хранить корневой узел

        root = self.array[0]

  

        # Заменить корневой узел последним узлом

        lastNode = self.array[self.size - 1]

        self.array[0] = lastNode

  

        # Обновить позицию последнего узла

        self.pos[lastNode[0]] = 0

        self.pos[root[0]] = self.size - 1

  

        # Уменьшить размер кучи и укрупнить корень

        self.size -= 1

        self.minHeapify(0)

  

        return root

  

    def isEmpty(self):

        return True if self.size == 0 else False

  

    def decreaseKey(self, v, dist):

  

        # Получить индекс v в массиве кучи

  

        i = self.pos[v]

  

        # Получить узел и обновить его значение dist

        self.array[i][1] = dist

  

        # Путешествуйте, пока полное дерево не

        # печально. Это цикл O (Logn)

        while i > 0 and self.array[i][1] < \

                    self.array[(i - 1) / 2][1]:

  

            # Поменяйте местами этот узел с его родителем

            self.pos[ self.array[i][0] ] = (i-1)/2

            self.pos[ self.array[(i-1)/2][0] ] = i

            self.swapMinHeapNode(i, (i - 1)/2 )

  

            # перейти к родительскому индексу

            i = (i - 1) / 2;

  

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

    # 'v' в минимальной куче или нет

    def isInMinHeap(self, v):

  

        if self.pos[v] < self.size:

            return True

        return False

  

  

def printArr(parent, n):

    for i in range(1, n):

        print "% d - % d" % (parent[i], i)

  

  

class Graph():

  

    def __init__(self, V):

        self.V = V

        self.graph = defaultdict(list)

  

    # Добавляет ребро в неориентированный граф

    def addEdge(self, src, dest, weight):

  

        # Добавить ребро из src в dest. Новый узел

        # добавлен в список смежности src. Узел

        # добавляется в начале. Первый элемент

        # узел имеет пункт назначения и второй

        # элементов имеет вес

        newNode = [dest, weight]

        self.graph[src].insert(0, newNode)

  

        # Так как график не является направленным, добавьте ребро из

        # dest to src также

        newNode = [src, weight]

        self.graph[dest].insert(0, newNode)

  

    # Основная функция, которая печатает минимум

    # Spanning Tree (MST) с использованием алгоритма Прима.

    # Это функция O (ELogV)

    def PrimMST(self):

        # Получить количество вершин в графе

        V = self.V  

          

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

        key = []   

          

        # Список для хранения созданного MST

        parent = [] 

  

        # minHeap представляет множество E

        minHeap = Heap()

  

        # Инициализировать минимальную кучу со всеми вершинами. Ключевые ценности всех

        # вершин (кроме 0-й вершины) изначально бесконечна

        for v in range(V):

            parent.append(-1)

            key.append(sys.maxint)

            minHeap.array.append( minHeap.newMinHeapNode(v, key[v]) )

            minHeap.pos.append(v)

  

        # Сделать значение ключа 0-й вершины равным 0, чтобы

        # что он извлекается первым

        minHeap.pos[0] = 0

        key[0] = 0

        minHeap.decreaseKey(0, key[0])

  

        # Первоначально размер min heap равен V

        minHeap.size = V;

  

        # В следующем цикле min heap содержит все узлы

        # еще не добавлено в MST.

        while minHeap.isEmpty() == False:

  

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

            newHeapNode = minHeap.extractMin()

            u = newHeapNode[0]

  

            # Пройдите через все смежные вершины

            # (извлеченная вершина) и обновить их

            # значения расстояния

            for pCrawl in self.graph[u]:

  

                v = pCrawl[0]

  

                # Если кратчайшее расстояние до v не завершено

                # еще, а расстояние до v через u меньше

                # его ранее рассчитанное расстояние

                if minHeap.isInMinHeap(v) and pCrawl[1] < key[v]:

                    key[v] = pCrawl[1]

                    parent[v] = u

  

                    # обновить значение расстояния в мин куче также

                    minHeap.decreaseKey(v, key[v])

  

        printArr(parent, V)

  

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

graph = Graph(9)

graph.addEdge(0, 1, 4)

graph.addEdge(0, 7, 8)

graph.addEdge(1, 2, 8)

graph.addEdge(1, 7, 11)

graph.addEdge(2, 3, 7)

graph.addEdge(2, 8, 2)

graph.addEdge(2, 5, 4)

graph.addEdge(3, 4, 9)

graph.addEdge(3, 5, 14)

graph.addEdge(4, 5, 10)

graph.addEdge(5, 6, 2)

graph.addEdge(6, 7, 1)

graph.addEdge(6, 8, 6)

graph.addEdge(7, 8, 7)

graph.PrimMST()

  
# Этот код предоставлен Divyanshu Mehta

Выход:

0 - 1
5 - 2
2 - 3
3 - 4
6 - 5
7 - 6
0 - 7
2 - 8

Сложность времени: временная сложность приведенного выше кода / алгоритма выглядит как O (V ^ 2), так как есть два вложенных цикла while. Если мы посмотрим поближе, то заметим, что операторы во внутреннем цикле выполняются O (V + E) раз (аналогично BFS). Во внутреннем цикле есть операция lowerKey (), которая занимает время O (LogV). Таким образом, общая сложность по времени составляет O (E + V) * O (LogV), которая равна O ((E + V) * LogV) = O (ELogV) (для связного графа V = O (E))

Ссылки:
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.

http://en.wikipedia.org/wiki/Prim's_algorithm

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

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

Prim's MST для представления списка смежности | Жадный Алго-6

0.00 (0%) 0 votes