Алгоритм Крускала — Вікіпедія

Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано Джозефом Крускалом^[en] 1956 року^[1].

Реалізація

Візьмемо зважений зв'язний граф G=(V, E), де V — множина вершин, E — множина ребер, для кожного з яких задано вагу. Тоді ациклічна множина ребер, що поєднують усі вершини графу і чия загальна вага мінімальна, називається мінімальним кістяковим деревом.

Алгоритм Крускала починається з побудови виродженого лісу, що містить V дерев, кожне з яких складається з однієї вершини. Далі виконуються операції об'єднання двох дерев, для чого використовуються найкоротші можливі ребра, поки не утвориться єдине дерево. Це дерево і буде мінімальним кістяковим деревом.

	Початковий граф. Цифри над ребрами позначають їх вагу. Жодне з ребер не додане до кістякового дерева.
	AD і CE мають найменшу вагу 5, і AD вибирається з них довільно та додається до кістякового дерева.
	На цьому кроці CE є найлегшим ребром з вагою 5, тому воно також додається до дерева.
	Аналогічним чином обирається найлегше з недоданих ребер графу DF з вагою 6 і додається до кістякового дерева.
	Наступними найлегшими ребрами є AB і BE, обидва вагою 7. AB обирається довільно і додається до кістякового дерева. BD фарбується у червоний колір, оскільки воно є частиною циклу ABD.
	Наступним додається ребро BE з вагою 7. Червоним забарвлюємо ребра BC (цикл BCE), DE (цикл DEBA) і FE (цикл FEBAD).
	Додаємо ребро EG вагою 9 і отримуємо мінімальне кістякове дерево.

Код на 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; }

Оцінка складності

Алгоритм Крускала (як і алгоритм Прима) є класичним алгоритмом розв'язання задачі пошуку мінімального кістякового дерева. У разі використання найшвидших реалізацій час його роботи становить $\mathop {O} (E\log E)$ ^[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); 	} }

Примітки

↑ Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50
↑ Рыбаков Г. (2005). Минимальные остовные деревья. Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 8 липня 2013. Процитовано 31 серпня 2011.

Посилання

Вікісховище має мультимедійні дані за темою: Алгоритм Крускала

[1] Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50

[2] Рыбаков Г. (2005). Минимальные остовные деревья. Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 8 липня 2013. Процитовано 31 серпня 2011.

[1]

[2]