streamalism.org

1. Prehľad

V predchádzajúcom článku sme predstavili Primov algoritmus na nájdenie minimálneho rozsahu stromov. V tomto článku použijeme na riešenie problémov s minimálnym a maximálnym rozpätím stromu iný prístup, Kruskalov algoritmus.

2. Spanning Tree

Rozpätím stromu neorientovaného grafu je pripojený podgraf, ktorý pokrýva všetky uzly grafu s minimálnym možným počtom hrán. Všeobecne môže mať graf viac ako jeden spanning tree. Nasledujúci obrázok zobrazuje graf s spanningovým stromom (okraje spanningového stromu sú červené):

Ak je graf okrajovo vážený, môžeme definovať váhu spanningového stromu ako súčet váh všetkých jeho hrán. Minimálny kostra je kostra, ktorej váha je najmenšia zo všetkých možných kostier. Nasledujúci obrázok zobrazuje minimálny rozpätie stromu v grafe s hraničnými hodnotami:

Podobne maximálny kostra má najväčšiu váhu zo všetkých kostier. Na nasledujúcom obrázku je maximálny rozpätie stromu v grafe s hraničnými hodnotami:

3. Kruskalov algoritmus

Na základe grafu môžeme použiť Kruskalov algoritmus na nájdenie jeho minimálneho rozsahu. Ak je počet uzlov v grafe V., potom by každý z jeho klenutých stromov mal mať (V-1) okraje a nemal by obsahovať žiadne cykly. Kruskalov algoritmus môžeme opísať v nasledujúcom pseudokódu:

Inicializujte prázdnu sadu hrán T. Zoraďte všetky hrany grafu podľa vzostupného poradia ich hodnôt hmotnosti. foreach edge in the ordered edge list Skontrolujte, či vytvorí cyklus s hranami vo vnútri T. Ak hrana nezavádza žiadne cykly, pridajte ju do T. Ak T má (V-1) hrany, ukončite slučku. návrat T

Spustime Kruskalov algoritmus pre minimálny rozsah stromu na našom vzorovom grafe krok za krokom:

Najskôr si vyberieme hranu (0, 2), pretože má najmenšiu váhu. Potom môžeme pridať hrany (3, 4) a (0, 1), pretože nevytvárajú žiadne cykly. Teraz je ďalším kandidátom hrana (1, 2) s hmotnosťou 9. Ak však zahrnieme túto hranu, vytvoríme cyklus (0, 1, 2). Preto túto hranu zahodíme a pokračujeme vo výbere ďalšej najmenšej. Nakoniec algoritmus končí pridaním okraja (2, 4) váhy 10.

Na výpočet maximálneho rozsahu stromu môžeme zmeniť poradie zostupného poradia. Ostatné kroky zostávajú rovnaké. Nasledujúci obrázok ukazuje postupnú konštrukciu stromu s maximálnym rozpätím na našom vzorovom grafe.

4. Detekcia cyklu s disjunktnou sadou

V Kruskalovom algoritme je najdôležitejšou časťou skontrolovať, či hrana vytvorí cyklus, ak ho pridáme do existujúcej množiny okrajov. Existuje niekoľko algoritmov detekcie cyklu grafov, ktoré môžeme použiť. Napríklad môžeme použiť algoritmus hĺbkového prieskumu (DFS) na prechádzanie grafom a zisťovanie, či existuje cyklus.

Potrebujeme však vykonať detekciu cyklu na existujúcich hranách zakaždým, keď testujeme novú hranu. Rýchlejším riešením je použitie algoritmu Union-Find s disjunktnou dátovou štruktúrou, pretože ten tiež existujepoužíva na detekciu cyklov prístup s prírastkovým okrajom. Môžeme to zapadnúť do procesu výstavby nášho stromu.

4.1. Nespojitá súprava a konštrukcia rozpätia stromu

Najprv považujeme každý uzol grafu za samostatnú množinu, ktorá obsahuje iba jeden uzol. Potom zakaždým, keď zavedieme hranu, skontrolujeme, či sú jej dva uzly v rovnakej množine. Ak je odpoveď áno, vytvorí sa cyklus. V opačnom prípade spojíme dve disjunktné množiny do jednej množiny a zahrnieme okraj pre spanning tree.

Vyššie uvedené kroky môžeme opakovať, kým zostrojíme celý spanning tree.

Napríklad vo vyššie uvedenej minimálnej konštrukcii rozloženého stromu máme najskôr 5 množín uzlov: {0}, {1}, {2}, {3}, {4}. Keď skontrolujeme prvý okraj (0, 2), jeho dva uzly sú v rôznych množinách uzlov. Preto môžeme zahrnúť tento okraj a zlúčiť {0} a {2} do jednej množiny {0, 2}.

Podobné operácie môžeme urobiť pre hrany (3, 4) a (0, 1). Množiny uzlov potom budú {0, 1, 2} a {3, 4}. Keď skontrolujeme ďalšiu hranu (1, 2), môžeme vidieť, že oba uzly tejto hrany sú v rovnakej množine. Preto túto hranu zahodíme a pokračujeme v kontrole ďalšej. Nakoniec hrana (2, 4) spĺňa naše podmienky a môžeme ju zahrnúť pre minimálny spanningový strom.

4.2. Implementácia nesúvislej množiny

Na vyjadrenie nesúvislej množiny môžeme použiť stromovú štruktúru. Každý uzol má a rodič ukazovateľ na odkaz na jeho nadradený uzol. V každej množine je jedinečný koreňový uzol, ktorý predstavuje túto množinu. Koreňový uzol má vlastnú referenciu rodič ukazovateľ.

Použime triedu Java na definovanie informácií o disjunktnej množine:

public class DisjointSetInfo {private Integer parentNode; DisjointSetInfo (celé číslo rodič) {setParentNode (rodič); } // štandardní zakladatelia a obstarávatelia}

Označme každý uzol grafu celým číslom, počnúc od 0. Môžeme použiť dátovú štruktúru zoznamu, Zoznam uzlov, na uloženie informácií o nesúvislej množine grafu. Na začiatku je každý uzol reprezentatívnym členom jeho vlastnej množiny:

void initDisjointSets (int totalNodes) {nodes = new ArrayList (totalNodes); for (int i = 0; i <totalNodes; i ++) {nodes.add (new DisjointSetInfo (i)); }} 

4.3. Nájdite operáciu

Aby sme našli množinu, do ktorej uzol patrí, môžeme sledovať nadradený reťazec uzla smerom hore, kým sa nedostaneme ku koreňovému uzlu:

Nájsť celé číslo (uzol celého čísla) {Celé číslo rodič = nodes.get (uzol) .getParentNode (); if (parent.equals (node)) {návratový uzol; } else {návrat nálezu (rodič); }}

Pre disjunktnú množinu je možné mať vysoko nevyváženú stromovú štruktúru. Môžeme vylepšiť Nájsť prevádzka pomocou ppri kompresii technika.

Pretože každý uzol, ktorý navštívime na ceste do koreňového uzla, je súčasťou rovnakej množiny, môžeme k nemu pripojiť koreňový uzol rodič odkaz priamo. Keď nabudúce navštívime tento uzol, potrebujeme jednu cestu na vyhľadanie koreňového uzla:

Celé číslo pathCompressionFind (celé číslo uzla) {DisjointSetInfo setInfo = nodes.get (uzol); Celé číslo rodič = setInfo.getParentNode (); if (parent.equals (node)) {návratový uzol; } else {Celé číslo parentNode = find (parent); setInfo.setParentNode (parentNode); návrat parentNode; }}

4.4. Operácia Únie

Ak sú dva uzly okraja v rôznych množinách, spojíme tieto dve množiny do jednej. Môžeme to dosiahnuť únie operácia nastavením koreňa jedného reprezentatívneho uzla do druhého reprezentatívneho uzla:

void union (Integer rootU, Integer rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); setInfoU.setParentNode (rootV); }

Táto jednoduchá operácia spojenia mohla vytvoriť vysoko nevyvážený strom, pretože sme vybrali náhodný koreňový uzol pre zlúčenú množinu. Výkon môžeme zlepšiť pomocou a únia podľa hodnosti technika.

Pretože je to hĺbka stromu, ktorá ovplyvňuje prevádzkovú dobu Nájsť prevádzka, súpravu s kratším stromom pripevníme k súprave s dlhším stromom. Táto technika zvyšuje iba hĺbku zlúčeného stromu, ak majú pôvodné dva stromy rovnakú hĺbku.

Aby sme to dosiahli, najskôr pridáme a hodnosť majetok do DisjointSetInfo trieda:

public class DisjointSetInfo {private Integer parentNode; hodnosť súkromného int; DisjointSetInfo (celé číslo rodič) {setParentNode (rodič); setRank (0); } // štandardní zakladatelia a obstarávatelia}

Na začiatku má disjunkt jedného uzla poradie 0. Počas zjednotenia dvoch množín sa koreňový uzol s vyššou hodnosťou stáva koreňovým uzlom zlúčenej množiny. Pozíciu nového koreňového uzla zvýšime o jednu, iba ak sú pôvodné dve hodnosti rovnaké:

void unionByRank (int rootU, int rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); DisjointSetInfo setInfoV = nodes.get (rootV); int rankU = setInfoU.getRank (); int rankV = setInfoV.getRank (); if (rankU <rankV) {setInfoU.setParentNode (rootV); } else {setInfoV.setParentNode (rootU); if (rankU == rankV) {setInfoU.setRank (rankU + 1); }}}

4.5. Detekcia cyklu

Porovnaním výsledkov dvoch môžeme určiť, či sú dva uzly v tej istej disjunktnej množine Nájsť operácie. Ak majú rovnaký reprezentatívny koreňový uzol, potom sme zistili cyklus. V opačnom prípade spojíme dve disjunktné množiny pomocou a únie prevádzka:

boolean detectCycle (Celé číslo u, Celé číslo v) {Celé číslo rootU = pathCompressionFind (u); Celé číslo rootV = pathCompressionFind (v); if (rootU.equals (rootV)) {return true; } unionByRank (rootU, rootV); návrat nepravdivý; } 

Detekcia cyklu pomocou únia podľa hodnosti samotná technika, má čas chodu O (logV). Oboma môžeme dosiahnuť lepší výkon kompresia cesty a únia podľa hodnosti techniky. Prevádzková doba je O (α (V)), kde α (V) je inverzná Ackermannova funkcia celkového počtu uzlov. Je to malá konštanta, ktorá je v našich výpočtoch v reálnom svete menej ako 5.

5. Implementácia Kruskalovho algoritmu v Jave

Môžeme použiť ValueGraph dátovú štruktúru v aplikácii Google Guava, ktorá predstavuje graf s váženými hranami.

Použit ValueGraph, najskôr musíme do projektu pridať závislosť Guava pom.xml spis:

     com.google.guava guava 28,1-jre 

Vyššie uvedené metódy detekcie cyklu môžeme zabaliť do a CycleDetector triedy a použiť ju v Kruskalovom algoritme. Pretože algoritmy stavby minimálneho a maximálneho rozloženého stromu majú iba mierny rozdiel, na dosiahnutie oboch konštrukcií môžeme použiť jednu všeobecnú funkciu:

ValueGraph spanningTree (graf ValueGraph, boolovský minSpanningTree) {Nastaviť hrany = graph.edges (); Zoznam edgeList = nový ArrayList (hrany); if (minSpanningTree) {edgeList.sort (Comparator.comparing (e -> graph.edgeValue (e) .get ())); } else {edgeList.sort (Collections.reverseOrder (Comparator.comparing (e -> graph.edgeValue (e) .get ()))); } int totalNodes = graph.nodes (). size (); CycleDetector cycleDetector = nový CycleDetector (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); pre (EndpointPair edge: edgeList) {if (cycleDetector.detectCycle (edge.nodeU (), edge.nodeV ())) {continue; } spanningTree.putEdgeValue (edge.nodeU (), edge.nodeV (), graph.edgeValue (edge) .get ()); edgeCount ++; if (edgeCount == totalNodes - 1) {break; }} návrat spanningTree; }

V Kruskalovom algoritme najskôr roztriedime všetky hrany grafu podľa ich váh. Táto operácia trvá O (ElogE) čas, kde E je celkový počet hrán.

Potom pomocou slučky prechádzame zoradeným okrajovým zoznamom. V každej iterácii kontrolujeme, či sa cyklus vytvorí pridaním okraja do aktuálnej množiny okrajov rozloženého stromu. Táto slučka s detekciou cyklu trvá najviac O (ElogV) čas.

Preto je celková doba prevádzky O (ELogE + ELogV). Od hodnoty E je v mierke O (V2), je časová zložitosť Kruskalovho algoritmu O (ElogE) alebo O (ElogV).

6. Záver

V tomto článku sme sa naučili, ako používať Kruskalov algoritmus na nájdenie minimálneho alebo maximálneho rozsahu grafu. Zdrojový kód článku je ako vždy k dispozícii na stránkach GitHub.