Алгоритм двох китайців — алгоритм побудови мінімального кістякового дерева в підвішеному орієнтованому графі з коренем в заданій вершині. Був розроблений математиками Чу Йонджіном і Лю Цзенхонгом.
Постановка задачі
Задано зважений орієнтований граф і початкова вершина
. Потрібно побудувати кореневе остовне дерево в
з коренем у вершині
, сума ваг усіх ребер якого мінімальна.
Алгоритм
Опис
Якщо хоча б одна вершина графу недосяжна з
, то необхідне дерево побудувати не можна.
|
Реалізація
Позначення:
- Граф зберігається у вигляді множини ребер + індекс кореня.
- Множина ребер - список суміжності.
- Ребро - структура {from, to, weight}.
- root - поточний корінь.
Особливість реалізації: алгоритмом не важлива кратність ребер, тому при складанні нового графу кратні ребра можуть з'явитися - це зменшує асимптотику з до
int findMST(edges, n, root): int res = 0 int minEdge[n] // створюємо масив мінімумів, що входять у кожну компоненту, ініціалізуємо нескінченністю. for eachminEdge[e.to] = min(e.w, minEdge[e.to]) for each
res += minEdge[v] //ваги мінімальних ребер точно будуть в результаті edge zeroEdges[] //створюємо масив нульових ребер for each
if e.w == minEdge[e.to] zeroEdges.pushback(
) //
- ребро е, зменшене на мінімальну вагу, що входить до e.to if dfs(root, zeroEdges) // перевіряємо, чи можна дійти до всіх вершин за нульовими ребрах return res int newComponents[n] // майбутні компоненти зв'язності newComponents = Condensation(zeroEdges) edge newEdges[] //створюємо масив ребер у новому графі з вершинами в отриманих компонентах for each
zeroEdges if e.to і e.from в різних компонентах додаємо в newEdges ребро з кінцями в даних компонентах і вагою e.w res += findMST(zeroEdges, ComponentsCount, newComponents[root]) return res
Складність
Всього буде побудовано не більше конденсацій. Конденсацію можна побудувати за
. Значить, алгоритм можна реалізувати за
.
Джерела
- Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. (233 страница) -
- http://is.ifmo.ru [Архівовано 20 квітня 2014 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm dvoh kitajciv algoritm pobudovi minimalnogo kistyakovogo dereva v pidvishenomu oriyentovanomu grafi z korenem v zadanij vershini Buv rozroblenij matematikami Chu Jondzhinom i Lyu Czenhongom Postanovka zadachiZadano zvazhenij oriyentovanij graf G V E displaystyle G V E i pochatkova vershina v displaystyle v Potribno pobuduvati koreneve ostovne derevo v G displaystyle G z korenem u vershini v displaystyle v suma vag usih reber yakogo minimalna AlgoritmOpis Yaksho hocha b odna vershina grafu G displaystyle G nedosyazhna z v displaystyle v to neobhidne derevo pobuduvati ne mozhna Dlya kozhnoyi vershini u v displaystyle u neq v grafu G displaystyle G zrobimo taku operaciyu znajdemo rebro minimalnoyi vagi sho vhodit do u displaystyle u i vidnimemo vagu cogo rebra z vag vsih reber sho vhodyat do u displaystyle u m u min t u E w t u w t u w t u m u displaystyle m u min limits tu in E w tu w tu w tu m u Buduyemo graf K V K 0 displaystyle K V K 0 de K 0 displaystyle K 0 mnozhina reber nulovoyi vagi grafu G displaystyle G z vagovoyu funkciyeyu w displaystyle w Yaksho v comu grafi znajdetsya kistyakove derevo z korenem u v displaystyle v to vono i bude shukanim Yaksho takogo dereva nemaye to pobuduyemo graf C displaystyle C kondensaciyu grafu K displaystyle K Nehaj y displaystyle y ta z displaystyle z dvi vershini grafu C displaystyle C vidpovidayuchi komponentam silnoj zv yaznosti Y displaystyle Y ta Z displaystyle Z grafu K displaystyle K vidpovidno Poklademo vagu rebra mizh vershinami y displaystyle y i z displaystyle z rivnoyu minimalnomu sered vag reber grafu G displaystyle G z vagovoyu funkciyeyu w displaystyle w sho idut z Y displaystyle Y v Z displaystyle Z Prodovzhimo z punktu 2 vikoristovuyuchi graf C displaystyle C zamist G displaystyle G U C displaystyle C pobudovano MST T displaystyle T Pobuduyemo teper MST T displaystyle T v G displaystyle G z vagovoyu funkciyeyu w displaystyle w Dodamo do T displaystyle T vsi vershini komponenti silnoyi zv yaznosti grafu K displaystyle K yakij nalezhit v displaystyle v po shlyahah nulovogo vagi z v displaystyle v Nehaj u T displaystyle T ye rebro y z displaystyle yz de y displaystyle y vidpovidaye komponenti silnoyi zv yaznosti Y displaystyle Y a z displaystyle z komponenti silnoyi zv yaznosti Z displaystyle Z grafu K displaystyle K Mizh Y displaystyle Y i Z displaystyle Z u grafi G displaystyle G z vagovoyu funkciyeyu w displaystyle w ye rebro y z displaystyle y z vaga yakogo dorivnyuye vazi rebra y z displaystyle yz Dodamo ce rebro do dereva T displaystyle T Dodamo do T displaystyle T vsi vershini komponenti Z displaystyle Z po shlyahah nulovogo vagi z z displaystyle z Zrobimo tak dlya kozhnogo rebra dereva T displaystyle T Otrimane derevo T displaystyle T MST v grafi G displaystyle G Realizaciya Poznachennya Graf zberigayetsya u viglyadi mnozhini reber indeks korenya Mnozhina reber spisok sumizhnosti Rebro struktura from to weight root potochnij korin Osoblivist realizaciyi algoritmom ne vazhliva kratnist reber tomu pri skladanni novogo grafu kratni rebra mozhut z yavitisya ce zmenshuye asimptotiku z O V 2 displaystyle O V 2 do O E displaystyle O E int findMST edges n root int res 0 int minEdge n stvoryuyemo masiv minimumiv sho vhodyat u kozhnu komponentu inicializuyemo neskinchennistyu for each e E displaystyle e in E minEdge e to min e w minEdge e to for each v V r o o t displaystyle v in V backslash root res minEdge v vagi minimalnih reber tochno budut v rezultati edge zeroEdges stvoryuyemo masiv nulovih reber for each e E displaystyle e in E if e w minEdge e to zeroEdges pushback e 1 displaystyle e 1 e 1 displaystyle e 1 rebro e zmenshene na minimalnu vagu sho vhodit do e to if dfs root zeroEdges pereviryayemo chi mozhna dijti do vsih vershin za nulovimi rebrah return res int newComponents n majbutni komponenti zv yaznosti newComponents Condensation zeroEdges edge newEdges stvoryuyemo masiv reber u novomu grafi z vershinami v otrimanih komponentah for each e displaystyle e in zeroEdges if e to i e from v riznih komponentah dodayemo v newEdges rebro z kincyami v danih komponentah i vagoyu e w res findMST zeroEdges ComponentsCount newComponents root return res Skladnist Vsogo bude pobudovano ne bilshe V displaystyle V kondensacij Kondensaciyu mozhna pobuduvati za O E displaystyle O E Znachit algoritm mozhna realizuvati za O V E displaystyle O VE DzherelaRomanovskij I V Diskretnyj analiz 3 e izd pererab i dop SPb Nevskij Dialekt BHV Peterburg 2003 320 s il 233 stranica ISBN 5 7940 0114 3 http is ifmo ru Arhivovano 20 kvitnya 2014 u Wayback Machine