Определение

Алгоритм Прима - алгоритм поиска минимального основного дерева во взвешенном графе.

---

Принцип работы алгоритма

Ниже представлены: граф - слева и его минимальное основное дерево - справа.

Берём произвольную вершину графа и находим минимальное ребро, которое с ней связано. Добавляем это ребро в дерево. Далее, пока не переберём все рёбра графа, производим следующие операции:

1. Из рёбер, которые связаны с деревом, выбираем минимальное.
2. Если оно не создаёт цикла, добавляем ребро в дерево.

В приведённом ниже примере начальная вершина - $A$

ИСХОДНЫЙ ГРАФ

---

Сложность

Сложность алгоритма: $O(V^2)$, где $V$ - количество вершин (узлов)

---

Псевдокод

 Aлгоритм Прима
    дерево <- пустой список
    посещённые узлы <- пустое множество
    добавляем в список посещённых случайный узел
    
    пока не посетм все узлы:
        мин_ребро <- Выбрать мин ребро(рёбра графа, посещённые узлы)
        добавляем мин_ребро в дерево
        
    вернуть дерево

 Выбрать мин ребро(рёбра графа, посещённые узлы)
    список ребёр <- пусто
    
    для ребра в рёбрах графа:
       если один из узлов ребра посещали
            то добавляем ребро в список
            
    мин_ребро <- минимальное ребро из списка рёбер
    добавляем узлы мин_ребра в список посещённых
    отчищаем список рёбер
    
    вернуть мин ребро

---

Реализация на Python

Аннотация:
min_edge - функция для нахождения ребра с минимальным весом, которое соединяет посещенные и непосещенные вершины.
visit - множество посещенных вершин.
edges - список всех ребер в графе (каждое ребро представлено кортежем из трех элементов: две вершины и вес ребра).
arr - список ребер, которые соединяют посещенные и непосещенные вершины.
min_ - ребро с минимальным весом среди тех, которые соединяют посещенные и непосещенные вершины.
prima - функция для нахождения минимального остовного дерева с помощью алгоритма Прима.
mst - общая стоимость минимального остовного дерева.

def min_edge(visit, edges):  
    arr = [] 
     
    for edge in edges:  
        if edge[0] in visit or edge[1] in visit:  
            if edge[0] not in visit or edge[1] not in visit:  
                arr.append(edge)  
                
    min_ = min(arr, key=lambda x: x[2])  
    visit.add(min_[1])  
    visit.add(min_[0])  
    
    return min_  
  
  
def prima(edges):  
    mst = 0  
    visit = {0}  
    
    while len(visit) != vtx:  
        mst += min_edge(visit, edges)[2]  
        
    return mst

---

Олимпиадная реализация на C++

Аннотация:
r_min_edge - функция для нахождения ребра с минимальным весом, которое соединяет посещенные и непосещенные вершины.
edges - вектор всех ребер в графе (каждое ребро представлено вектором из трех элементов: две вершины и вес ребра).
visit - множество посещенных вершин.
arr - вектор ребер, которые соединяют посещенные и непосещенные вершины.
min_edge - ребро с минимальным весом среди тех, которые соединяют посещенные и непосещенные вершины.
prima - функция для нахождения минимального остовного дерева с помощью алгоритма Прима.
vtx - количество вершин в графе.
mst - общая стоимость минимального остовного дерева.

typedef vector<int> vi;
typedef set<int> si;

vi r_min_edge(vector<vi> edges, si visit) {
    vector<vi> arr;
    
    for (vi edge : edges) {
        if ((visit.count(edge[0]) != 0) 
		        || (visit.count(edge[1]) != 0)) {
            
            if ((visit.count(edge[0])) == 0 
		            || (visit.count(edge[1])) == 0) {
                arr.push_back(edge);
            }
        }
    };
    
    sort(arr.begin(), arr.end(), comp);
    vi min_edge = arr[0];
    arr.clear();
    
    return min_edge;
}

int prima(vector<vi> edges, si visit, int vtx) {
    int mst = 0;
    
    while (visit.size() != vtx) {
        vi min_edge = r_min_edge(edges, visit);
        mst += min_edge[2];
        visit.insert(min_edge[0]);
        visit.insert(min_edge[1]);
    };
    return mst;
}

---

Продуктовая реализация на C++

Аннотация:
Graph - класс, представляющий граф.
list_edges_graph - список всех ребер графа.
count_nodes_graph - количество вершин в графе.
prima_tree - объект, представляющий минимальное остовное дерево, в которое добавляются ребра.
tree_prima - метод, реализующий алгоритм Прима для нахождения минимального остовного дерева.
null_vector - пустой вектор, используемый для возврата в случае ошибки.
edges - вектор всех ребер графа.
node_visit - множество посещенных вершин.
get_random_node - метод для получения случайной вершины графа.
return_min_edge - метод для нахождения ребра с минимальным весом, которое соединяет посещенные и непосещенные вершины.
Edge - структура, представляющая ребро графа.
from - начальная вершина ребра.
to - конечная вершина ребра.
compare - функция сравнения двух ребер по их весу.
return_min_edge - метод класса Graph для нахождения ребра с минимальным весом, которое соединяет посещенные и непосещенные вершины.
vector_edges - вектор ребер, которые соединяют посещенные и непосещенные вершины.
min_edge - ребро с минимальным весом среди тех, которые соединяют посещенные и непосещенные вершины.

vector <Edge> Graph::tree_prima() {
    vector <Edge> null_vector;
    vector <Edge> edges = list_edges_graph;
    set <int> node_visit;
    node_visit.insert(get_random_node());
    while (node_visit.size() != count_nodes_graph) {
        Edge min_edge = return_min_edge(edges, node_visit);
        prima_tree.append_edge(min_edge);
        node_visit.insert(min_edge.from);
        node_visit.insert(min_edge.to);
    };
    return prima_tree.get_list_edges_tree();
}

Edge Graph::return_min_edge(vector <Edge> edges, set <int> node_visit) {
    vector <Edge> vector_edges;
    for (Edge edge : edges) {
        if ((node_visit.count(edge.from) != 0) 
		        || (node_visit.count(edge.to) != 0)) {
            if ((node_visit.count(edge.from)) == 0 
		            || (node_visit.count(edge.to)) == 0) {
                vector_edges.push_back(edge);
            }
        }
    }; 
    sort(vector_edges.begin(), vector_edges.end(), compare);
    
    Edge min_edge = vector_edges[0];
    vector_edges.clear();
    return min_edge;
}