Алгоритм Прима

[Шляпадляменя]

Помогите дописать алгоритм Прима по псевдокоду:
Алгоритм Прима:

G - граф, s - стартовая вершина
MinWeight - ассоциативный массив, хранящий для каждой вершины вес минимального ребра, соединяющего ее с вершиной в дереве
Parent - ассоциативный массив, хранящий для каждой вершины ее предка в минимальном остовном дереве
Weight(u, v) - вес ребра (u, v)
Prim(G, s):    
    Для каждой вершины v графа G:
        MinWeight[v] = Infinity
    MinWeight[s] = 0
    Q = G.V
    Пока Q не пусто:
        u = извлечь вершину из Q с минимальным значением MinWeight
        Для каждой вершины v смежной с u:
            Если v в Q и MinWeight[v] > Weight(u, v):
                MinWeight[v] = Weight(u, v)
                Parent[v] = u
    MST = {} - ребра минимального остовного дерева
    Для каждой вершины v графа G:
        Добавить ребро (v, Parent[v]) в MST
    Вернуть MST как результат

Код:

#include "min_spanning_tree.h"

using namespace std;

vector<pair<int, int>> min_spanning_tree(const Graph& graph) {
    map<int, double> MinWeight;
    map<int, int>  Parent;
    vector<int>Q, K;
    vector<int> MST;
    int u, s;
    for (int v = 0; v < graph.get_vertices().size(); v++) {
        MinWeight[v] = INFINITY;
    }
    MinWeight[s] = 0;
    Q = graph.get_vertices();
    vector <int>::iterator it, it_min;
    while (!Q.empty()) {
        int i;
        double min = MinWeight[Q[0]];
        it_min = Q.begin();
        for (it = Q.begin() + 1; it != Q.end(); it++) {
            if (MinWeight[*it] < min) {
                min = MinWeight[*it];
                it_min = it;
            }
        }
        u = *it_min;
        Q.erase(it_min);
        K = graph.get_adjacent_vertices(u);
        for (int i = 0; i < K.size(); i++) {
            if ( find(Q.begin(),Q.end(),K) != Q.end() & MinWeight[K[i]] > graph.edge_weight(u, K[i])) {
                MinWeight[K[i]] = graph.edge_weight(u, K[i]);
                Parent[K[i]] = u;
            }
        }
    }
    for (int v = 0; v < graph.get_vertices().size(); v++) {
        MST.push_back(v);
    }
    return MST;
}

граф:

#pragma once
#include <map>
#include <vector>
#include <tuple>
#include <initializer_list>

/**
 * Non-oriented weighted graph.
**/
class Graph {
public:
    Graph() {}
    Graph(std::initializer_list<std::tuple<int, int, double>> edges);

    /// Add single vertex to the graph.
    void add_vertex(int vertex);

    /// Add vertices (if necessary) and an edge between them to the graph.
    void add_edge(int start_vertex, int end_vertex, double weight = 1.0);

    /// Return all vertices of the graph.
    std::vector<int> get_vertices() const;

    /// Return all adjacent by edges vertices for the specified vertex.
    std::vector<int> get_adjacent_vertices(int src_vertex) const;

    /// Get adjacent edges for the vertex as vector of (end vertex, edge weight).
    std::vector<std::pair<int, double>> get_adjacent_edges(int src_vertex) const;

    /// Return true if the vertex exists in the graph, false otherwise.
    bool has_vertex(int vertex) const;

    /// Return true if vertices exist and have an edge between them, false otherwise.
    bool has_edge(int start_vertex, int end_vertex) const;

    /// Return weight of an edge between vertices (if there is any), throw an exception otherwise.
    double edge_weight(int start_vertex, int end_vertex) const;

    /// Remove the vertex and all its adjacent edges from the graph.
    void remove_vertex(int vertex);

    /// Remove the edge from the graph (but not the vertices).
    void remove_edge(int start_vertex, int end_vertex);

private:
    std::map<int, std::map<int, double>> vertices;
};

[Шляпадляменя]

больше не актуальна