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

O(V²)

int prim(vector<vector<Edge>> &graph) {
    vector<bool> visited(graph.size());
    vector<int> dist(graph.size(), 1e9);
    dist[0] = 0;

    int mstWeight = 0;

    for (int i = 0; i < graph.size(); i++) {
        int nearestV = -1;
        for (int v = 0; v < graph.size(); v++)
            if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV]))
                nearestV = v;

        visited[nearestV] = true;
        mstWeight += dist[nearestV];

        for (auto &[from, to, weight] : graph[nearestV])
            if (dist[to] > weight)
                dist[to] = weight;
    }

    return mstWeight;
}

Полностью аналогично реализации Дейкстры за O(V²).

Единственная разница — в качестве расстояния до вершины используется длина не всего пути, а последнего ребра.

O(ElogV)

int prim(vector<vector<Edge>> &graph) {
    vector<bool> visited(graph.size());
    vector<int> dist(graph.size(), 1e9);
    set<pair<int, int>> unvisited;
    dist[0] = 0;
    unvisited.insert({ dist[0], 0 });

    int mstWeight = 0;

    while (!unvisited.empty()) {
        int nearestV = unvisited.begin()->second;
        unvisited.erase(unvisited.begin());

        visited[nearestV] = true;
        mstWeight += dist[nearestV];

        for (auto &[from, to, weight] : graph[nearestV]) {
            if (!visited[to] && dist[to] > weight) {
                unvisited.erase({ dist[to], to });
                dist[to] = weight;
                unvisited.insert({ dist[to], to });
            }
        }
    }

    return mstWeight;
}

Почти аналогично реализации Дейкстры за O(ElogV).

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

В отличие от Дейкстры, использование visited обязательно (контртест — 1 2 2, 2 3 1).

Ссылки

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

Ссылки

Навигация

Поиск