Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Алгоритм Краскала

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

Жадно добавляем рёбра. Для эффективности используем систему непересекающихся множеств.

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


Листинг C++

class edge 
{
public :
    int i, j, r;
    edge (int _i = 0, int _j = 0, int _r = 0) : i (_i), j (_j), r (_r) {};
};
bool operator < (edge a, edge b) { return a.r < b.r; }

int kruskal (int n, vector < edge > R, vector < edge > &res)
{
    int weight = 0;
    res.assign (n, 0);
    diset s = diset (n);
    sort (R.begin (), R.end ());

    for (int i = 0; i < R.size (); ++ i)
        if (s.find_set (R[i].i) != s.find_set (R[i].j))
        {
            weight += R[i].r;
            res.push_back (R[i]);
            s.union_set (R[i].i, R[i].j);
        }
    return weight;
}

31.08.2008, 16:32