|
Алгоритм КрускалаАлгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано Джозефом Крускалом[en] 1956 року[1]. РеалізаціяВізьмемо зважений зв'язний граф G=(V, E), де V — множина вершин, E — множина ребер, для кожного з яких задано вагу. Тоді ациклічна множина ребер, що поєднують усі вершини графу і чия загальна вага мінімальна, називається мінімальним кістяковим деревом. Алгоритм Крускала починається з побудови виродженого лісу, що містить V дерев, кожне з яких складається з однієї вершини. Далі виконуються операції об'єднання двох дерев, для чого використовуються найкоротші можливі ребра, поки не утвориться єдине дерево. Це дерево і буде мінімальним кістяковим деревом.
Код на C++int cn; //число вершин
vector< vector<int> > ady; //матриця суміжності
// Повертає матрицю суміжності мінімального дерева
vector< vector<int> > Grafo :: kruskal(){
vector< vector<int> > adyacencia = this->ady;
vector< vector<int> > arbol(cn);
vector<int> pertenece(cn); // позначає, чи належить дереву вершина
for(int i = 0; i < cn; i++){
arbol[i] = vector<int> (cn, INF);
pertenece[i] = i;
}
int nodoA;
int nodoB;
int arcos = 1;
while(arcos < cn){
// Знайти найлегше ребро, що не утворює циклів і зберегти вершини і вагу.
int min = INF;
for(int i = 0; i < cn; i++)
for(int j = 0; j < cn; j++)
if(min > adyacencia[i][j] && pertenece[i] != pertenece[j] && adyacencia[i][j] != 0){
min = adyacencia[i][j];
nodoA = i;
nodoB = j;
}
// Якщо вершини не належать до одного дерева, додаємо ребро між ними до дерева.
if(pertenece[nodoA] != pertenece[nodoB]){
arbol[nodoA][nodoB] = min;
arbol[nodoB][nodoA] = min;
// Усі вершини дерева nodoB зараз належать до дерева nodoA.
int temp = pertenece[nodoB];
pertenece[nodoB] = pertenece[nodoA];
for(int k = 0; k < cn; k++)
if(pertenece[k] == temp)
pertenece[k] = pertenece[nodoA];
arcos++;
}
}
return arbol;
}
Оцінка складностіАлгоритм Крускала (як і алгоритм Прима) є класичним алгоритмом розв'язання задачі пошуку мінімального кістякового дерева. У разі використання найшвидших реалізацій час його роботи становить [2]. Основна частина часу витрачається на сортування ребер за вагою. Мінімальне кістякове дерево. Алгоритм Крускала з системою неперетинних множинТут буде розглянута реалізація з використанням структури даних «система неперетинних множин» (DSU), яка дозволить досягти асимптотики O (M log N). ОписТак само, як і в простій версії алгоритму Крускала, відсортуємо всі ребра за вагою у неспадному порядку. Потім помістимо кожну вершину в своє дерево (тобто свою множину) за допомогою виклику функції DSU MakeSet — на це піде в сумі O(N). Перебираємо всі ребра (у порядку сортування) і для кожного ребра за O(1) визначаємо, чи належать його кінці різних деревам (за допомогою двох викликів FindSet за O(1)). Нарешті, об'єднання двох дерев буде здійснюватися викликом функції Union — також за O(1). Разом ми отримуємо асимптотику O (M log N + N + M) = O (M log N). РеалізаціяДля зменшення обсягу коду реалізуємо всі операції не у вигляді окремих функцій, а прямо в коді алгоритму Крускала. Тут буде використовуватися рандомізована версія DSU. vector<int> p (n);
int dsu_get (int v) {
return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));
}
void dsu_unite (int a, int b) {
a = dsu_get (a);
b = dsu_get (b);
if (rand() & 1)
swap (a, b);
if (a != b)
p[a] = b;
}
int m;
vector < pair < int, pair<int,int> > > g;
int cost = 0;
vector < pair<int,int> > res;
sort (g.begin(), g.end());
p.resize (n);
for (int i=0; i<n; ++i)
p[i] = i;
for (int i=0; i<m; ++i) {
int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
if (dsu_get(a) != dsu_get(b)) {
cost += l;
res.push_back (g[i].second);
dsu_unite (a, b);
}
}
Примітки
Посилання Вікісховище має мультимедійні дані за темою: Алгоритм Крускала |
