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

Необходимо в заданном графе найти дерево, содержащее все вершины графа и имеющее минимальный суммарный вес рёбер.

Алгоритм Прима жадный - на каждой итерации необходимо добавлять ребро минимального веса, связывающее вершину, непринадлежащую дереву, с деревом.

Реализации алгоритмов Прима и Дейкстры различаются буквально тремя строчками.

Асимптотика O(N²).

Листинг C++

const int inf = 1e9;
void prim (int x, vector < vector < int > > &D, vector < int > &w, vector < int > &p)
{
    // initialization
    int i, j;
    int n = D.size ();
    vector < int > a (n, 0);
    w.assign (n, inf);
    p.assign (n, x);
    for (i = 0; i < n; ++ i)
            w[i] = D[x][i];
    a[x] = 1;
    w[x] = 0;
    p[x] = - 1;

    for (i = 0; i < n; ++ i)
    {
        // iMin - the closest not considered vertice
        int iMin = - 1, Min = inf;
        for (j = 0; j < n; ++ j)
            if (!a[j] && w[j] < Min)
            {
                iMin = j;
                Min = w[j];
            }

        if (iMin == - 1)
            return;
        a[iMin] = 1;

        // relaxation
        for (j = 0; j < n; ++ j)
            if (w[j] > D[iMin][j])
            {
                w[j] = D[iMin][j];
                p[j] = iMin;
            }
    }
}

21.05.2007, 18:43

По всем вопросам обращаться: rumterg@gmail.com