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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Реалізація[ред.ред. код]

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


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

Prim Algorithm 0.svg Початковий граф. Цифри над ребрами позначають їх вагу. Жодне з ребер не додане до остовного дерева.
Kruskal Algorithm 1.svg AD і CE мають найменшу вагу 5, і AD вибирається з них довільно та додається до остовного дерева.
Kruskal Algorithm 2.svg На цьому кроці CE є найлегшим ребром з вагою 5, тому воно також додається до дерева.
Kruskal Algorithm 3.svg Аналогічним чином обирається найлегше з недоданих ребер графа DF з вагою 6 і додається до остовного дерева.
Kruskal Algorithm 4.svg Наступними найлегшими ребрами є AB і BE, обидва вагою 7. AB обирається довільно і додається до остовного дерева. BD фарбується у червоний колір, оскільки воно є частиною циклу ABD.
Kruskal Algorithm 5.svg Наступним додається ребро BE з вагою 7. Червоним забарвлюємо ребра BC (цикл BCE), DE (цикл DEBA) і FE (цикл FEBAD).
Kruskal Algorithm 6.svg Додаємо ребро 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]){
                    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);
	}
}

Посилання[ред.ред. код]

  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). «Минимальные остовные деревья». Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 2013-07-08.