Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано [en] 1956 року.
Реалізація
Візьмемо зважений зв'язний граф 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; }
Оцінка складності
Алгоритм Крускала (як і алгоритм Прима) є класичним алгоритмом розв'язання задачі пошуку мінімального кістякового дерева. У разі використання найшвидших реалізацій час його роботи становить . Основна частина часу витрачається на сортування ребер за вагою.
Мінімальне кістякове дерево. Алгоритм Крускала з системою неперетинних множин
Тут буде розглянута реалізація з використанням структури даних «система неперетинних множин» (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.
Посилання
Вікісховище має мультимедійні дані за темою: Алгоритм Крускала |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Kruskala algoritm pobudovi minimalnogo kistyakovogo dereva zvazhenogo neoriyentovnogo grafu Algoritm bulo vpershe opisano en 1956 roku RealizaciyaVizmemo zvazhenij zv yaznij graf G V E de V mnozhina vershin E mnozhina reber dlya kozhnogo z yakih zadano vagu Todi aciklichna mnozhina reber sho poyednuyut usi vershini grafu i chiya zagalna vaga minimalna nazivayetsya minimalnim kistyakovim derevom Algoritm Kruskala pochinayetsya z pobudovi virodzhenogo lisu sho mistit V derev kozhne z yakih skladayetsya z odniyeyi vershini Dali vikonuyutsya operaciyi ob yednannya dvoh derev dlya chogo vikoristovuyutsya najkorotshi mozhlivi rebra poki ne utvoritsya yedine derevo Ce derevo i bude minimalnim kistyakovim derevom Pochatkovij graf Cifri nad rebrami poznachayut yih vagu Zhodne z reber ne dodane do kistyakovogo dereva AD i CE mayut najmenshu vagu 5 i AD vibirayetsya z nih dovilno ta dodayetsya do kistyakovogo dereva Na comu kroci CE ye najlegshim rebrom z vagoyu 5 tomu vono takozh dodayetsya do dereva Analogichnim chinom obirayetsya najlegshe z nedodanih reber grafu DF z vagoyu 6 i dodayetsya do kistyakovogo dereva Nastupnimi najlegshimi rebrami ye AB i BE obidva vagoyu 7 AB obirayetsya dovilno i dodayetsya do kistyakovogo dereva BD farbuyetsya u chervonij kolir oskilki vono ye chastinoyu ciklu ABD Nastupnim dodayetsya rebro BE z vagoyu 7 Chervonim zabarvlyuyemo rebra BC cikl BCE DE cikl DEBA i FE cikl FEBAD Dodayemo rebro EG vagoyu 9 i otrimuyemo minimalne kistyakove derevo Kod na C int cn chislo vershin vector lt vector lt int gt gt ady matricya sumizhnosti Povertaye matricyu sumizhnosti minimalnogo dereva vector lt vector lt int gt gt Grafo kruskal vector lt vector lt int gt gt adyacencia this gt ady vector lt vector lt int gt gt arbol cn vector lt int gt pertenece cn poznachaye chi nalezhit derevu vershina for int i 0 i lt cn i arbol i vector lt int gt cn INF pertenece i i int nodoA int nodoB int arcos 1 while arcos lt cn Znajti najlegshe rebro sho ne utvoryuye cikliv i zberegti vershini i vagu int min INF for int i 0 i lt cn i for int j 0 j lt cn j if min gt adyacencia i j amp amp pertenece i pertenece j amp amp adyacencia i j 0 min adyacencia i j nodoA i nodoB j Yaksho vershini ne nalezhat do odnogo dereva dodayemo rebro mizh nimi do dereva if pertenece nodoA pertenece nodoB arbol nodoA nodoB min arbol nodoB nodoA min Usi vershini dereva nodoB zaraz nalezhat do dereva nodoA int temp pertenece nodoB pertenece nodoB pertenece nodoA for int k 0 k lt cn k if pertenece k temp pertenece k pertenece nodoA arcos return arbol Ocinka skladnostiAlgoritm Kruskala yak i algoritm Prima ye klasichnim algoritmom rozv yazannya zadachi poshuku minimalnogo kistyakovogo dereva U razi vikoristannya najshvidshih realizacij chas jogo roboti stanovit O E log E displaystyle mathop O E log E Osnovna chastina chasu vitrachayetsya na sortuvannya reber za vagoyu Minimalne kistyakove derevo Algoritm Kruskala z sistemoyu neperetinnih mnozhinDokladnishe Minimalne kistyakove derevo Tut bude rozglyanuta realizaciya z vikoristannyam strukturi danih sistema neperetinnih mnozhin DSU yaka dozvolit dosyagti asimptotiki O M log N Opis Tak samo yak i v prostij versiyi algoritmu Kruskala vidsortuyemo vsi rebra za vagoyu u nespadnomu poryadku Potim pomistimo kozhnu vershinu v svoye derevo tobto svoyu mnozhinu za dopomogoyu vikliku funkciyi DSU MakeSet na ce pide v sumi O N Perebirayemo vsi rebra u poryadku sortuvannya i dlya kozhnogo rebra za O 1 viznachayemo chi nalezhat jogo kinci riznih derevam za dopomogoyu dvoh viklikiv FindSet za O 1 Nareshti ob yednannya dvoh derev bude zdijsnyuvatisya viklikom funkciyi Union takozh za O 1 Razom mi otrimuyemo asimptotiku O M log N N M O M log N Realizaciya Dlya zmenshennya obsyagu kodu realizuyemo vsi operaciyi ne u viglyadi okremih funkcij a pryamo v kodi algoritmu Kruskala Tut bude vikoristovuvatisya randomizovana versiya DSU vector lt int gt 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 amp 1 swap a b if a b p a b int m vector lt pair lt int pair lt int int gt gt gt g int cost 0 vector lt pair lt int int gt gt res sort g begin g end p resize n for int i 0 i lt n i p i i for int i 0 i lt 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 PrimitkiJoseph 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 Rybakov G 2005 Minimalnye ostovnye derevya Sankt Peterburgskij gosudarstvennyj universitet informacionnyh tehnologij mehaniki i optiki fakultet informacionnyh tehnologij i programmirovaniya kafedra kompyuternyh tehnologij diskretnaya matematika algoritmy Arhiv originalu za 8 lipnya 2013 Procitovano 31 serpnya 2011 PosilannyaVikishovishe maye multimedijni dani za temoyu Algoritm Kruskala