Алгоритм Прима: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
{| width="100%"
| width="50%"  |
'''O(V<sup>2</sup>)'''
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] > {{Changed|weight}})
                dist[to] = {{Changed|weight}};
    }
    return mstWeight;
}
Полностью аналогично реализации Дейкстры за O(V<sup>2</sup>).
Единственная разница — в качестве расстояния до вершины используется длина не всего пути, а последнего ребра.
| width="50%"  |
'''O(ElogV)'''
int prim(vector<vector<Edge>> &graph) {
    {{Changed|1=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());
        {{Changed|1=visited[nearestV] = true;}}
        mstWeight += dist[nearestV];
        for (auto &[from, to, weight] : graph[nearestV]) {
            if ({{Changed|!visited[to]}} && dist[to] > {{Changed|weight}}) {
                unvisited.erase({ dist[to], to });
                dist[to] = {{Changed|weight}};
                unvisited.insert({ dist[to], to });
            }
        }
    }
    return mstWeight;
}
Почти аналогично реализации Дейкстры за O(ElogV).
В качестве расстояния до вершины используется длина не всего пути, а последнего ребра.
В отличие от Дейкстры, использование visited обязательно (контртест — 1 2 2, 2 3 1).
|}
== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/mst_prim e-maxx.ru &mdash; Алгоритм Прима]
* [http://e-maxx.ru/algo/mst_prim e-maxx.ru &mdash; Алгоритм Прима]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Прима]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Прима]
* [http://brestprog.neocities.org/lections/mst.html brestprog.neocities.org &mdash; Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала)]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 8]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 8]
* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures &mdash; 4.3 Minimum Spanning Trees]
* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures &mdash; 4.3 Minimum Spanning Trees]

Текущая версия от 03:52, 26 декабря 2021

O(V2)

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(V2).

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

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

Ссылки