streamalism.org

1. Áttekintés

Egy korábbi cikkünkben bemutattuk Prim algoritmusát a legkisebb átívelő fák megtalálásához. Ebben a cikkben egy másik megközelítést, Kruskal algoritmusát fogjuk használni a minimális és maximális átívelő fa problémák megoldására.

2. Feszítő fa

A nem irányított gráf átívelő fája összekapcsolt algráf, amely az összes gráfcsomópontot a lehető legkevesebb éllel fedi. Általában egy grafikonnak több fája lehet. A következő ábra egy átfogó fát ábrázoló grafikont mutat (az átfogó fa széle piros színű):

Ha a gráf éllel súlyozott, akkor az átívelő fa súlyát az összes éle súlyának összegeként definiálhatjuk. A minimális átnyúló fa olyan átfogó fa, amelynek súlya a legkisebb az összes lehetséges átnyúló fa között. A következő ábra egy minimális átfogó fát mutat egy éllel súlyozott grafikonon:

Hasonlóképpen, egy maximális átnyúló fának van a legnagyobb súlya az összes átnyúló fa között. A következő ábra a maximális átfogó fát mutatja egy éllel súlyozott grafikonon:

3. Kruskal-algoritmus

Egy grafikon alapján Kruskal algoritmusát használhatjuk a legkisebb átfogó fa megtalálásához. Ha a grafikon csomópontjainak száma: V, akkor minden átnyúló fájának (V-1) élekkel kell rendelkeznie, és nem tartalmazhatnak ciklusokat. Kruskal algoritmusát a következő álkóddal írhatjuk le:

Inicializáljon egy üres élkészletet T. Rendezze az összes gráf élét súlyértékük növekvő sorrendje szerint. foreach él a rendezett éllistában Ellenőrizze, hogy létrejön-e egy ciklus a T élekkel. Ha az él nem vezet be ciklust, adja hozzá a T-be. Ha T-nek vannak (V-1) élei, lépjen ki a hurokból. vissza T

Futtassuk Kruskal algoritmusát egy minimális átfogó fára lépésről lépésre a mintagrafikonon:

Először az élt választjuk (0, 2), mert annak a legkisebb a súlya. Ezután felvehetjük a (3, 4) és (0, 1) éleket, mivel ezek nem hoznak létre ciklust. Most a következő jelölt az (1, 2) él, amelynek súlya 9. Ha azonban beleszámítjuk ezt az élt, akkor létrehozunk egy ciklust (0, 1, 2). Ezért ezt az évet elvetjük, és folytatjuk a következő legkisebb választását. Végül az algoritmus a 10 súlyú él (2, 4) hozzáadásával fejeződik be.

A maximális átfogó fa kiszámításához megváltoztathatjuk a rendezési sorrendet csökkenő sorrendre. A többi lépés ugyanaz marad. Az alábbi ábra a maximális átfogó fa lépésenkénti felépítését mutatja be mintagrafikonunk.

4. Ciklusérzékelés diszjunkt készlettel

Kruskal algoritmusában a legfontosabb rész annak ellenőrzése, hogy egy él létrehoz-e ciklust, ha hozzáadjuk a meglévő élkészlethez. Számos gráfciklus-detektáló algoritmus használható. Például egy mélység-első keresés (DFS) algoritmust használhatunk a grafikon áthaladásához és annak megállapításához, hogy van-e ciklus.

Ugyanakkor minden egyes alkalommal új ciklust kell detektálnunk a meglévő éleken, amikor új élt tesztelünk. Gyorsabb megoldás az Union-Find algoritmus használata a disszjunkt adatszerkezettel, mert az isnövekményes él hozzáadású megközelítést alkalmaz a ciklusok detektálására. Ezt beilleszthetjük az átfogó faépítési folyamatunkba.

4.1. Diszjunkt halmaz és átívelő fa építése

Először is, a grafikon minden csomópontját egyedi halmazként kezeljük, amely csak egy csomópontot tartalmaz. Ezután minden egyes él bevezetésekor ellenőrizzük, hogy két csomópontja ugyanabban a halmazban van-e. Ha a válasz igen, akkor ez ciklust hoz létre. Ellenkező esetben a két diszjunkt halmazt egy halmazba egyesítjük, és belefoglaljuk az átívelő fa szélét.

Megismételhetjük a fenti lépéseket, amíg meg nem állítjuk az egész átfogó fát.

Például a fenti minimális átívelő fa konstrukcióban először 5 csomópontkészletünk van: {0}, {1}, {2}, {3}, {4}. Amikor ellenőrizzük az első élt (0, 2), két csomópontja különböző csomópontkészletekben található. Ezért felvehetjük ezt az élt, és egyesíthetjük {0} és {2} egy halmazba {0, 2}.

Hasonló műveleteket hajthatunk végre a (3, 4) és (0, 1) éleknél is. A csomópontkészletek ekkor {0, 1, 2} és {3, 4} lesznek. Amikor ellenőrizzük a következő élt (1, 2), láthatjuk, hogy ennek az élnek mindkét csomópontja ugyanabban a halmazban van. Ezért ezt az évet elvetjük, és folytatjuk a következő ellenőrzését. Végül a (2, 4) él kielégíti a feltételünket, és felvehetjük a minimális fára is.

4.2. Disjoint Set implementáció

Fa struktúrát használhatunk a diszjunkt halmaz ábrázolására. Minden csomópontnak van egy szülő mutató hivatkozik a szülőcsomópontjára. Minden halmazban található egy egyedi gyökércsomópont, amely ezt a halmazt képviseli. A gyökércsomópont saját hivatkozással rendelkezik szülő mutató.

Használjunk Java osztályt a diszjunkt halmaz információinak meghatározásához:

public class DisjointSetInfo {private Integer parentNode; DisjointSetInfo (Egész szülő) {setParentNode (szülő); } // szabványos beállítók és szerelők}

Címkézzünk minden gráfcsomópontot 0-tól kezdődően egész számmal. Használhatunk egy lista adatstruktúrát, Sorolja fel a csomópontokat, a grafikon diszjunkt halmazinformációinak tárolásához. Kezdetben minden csomópont a saját készletének reprezentatív tagja:

void initDisjointSets (int totalNodes) {csomópontok = new ArrayList (totalNodes); for (int i = 0; i <totalNodes; i ++) {csomópontok.add (új DisjointSetInfo (i)); }} 

4.3. Keresse meg a műveletet

Ahhoz, hogy megtalálja azt a halmazt, amelyhez egy csomópont tartozik, követhetjük a csomópont szülőláncát felfelé, amíg el nem érjük a gyökércsomópontot:

Egész keresés (Egész csomópont) {Egész szülő = csomópontok.get (csomópont) .getParentNode (); if (szülő.egyenlő (csomópont)) {visszatér csomópont; } else {return find (szülő); }}

Lehetséges, hogy egy diszjunkt halmaz esetében nagyon kiegyensúlyozatlan fa szerkezet legyen. Javíthatjuk a megtalálja műveletet a oath tömörítés technika.

Mivel minden, a gyökércsomópont felé vezető úton meglátogatott csomópont ugyanazon készlet része, csatolhatjuk a gyökércsomópontot szülő közvetlenül hivatkozni. Amikor legközelebb meglátogatjuk ezt a csomópontot, egy keresési útvonalra van szükségünk a gyökércsomópont megszerzéséhez:

Integer pathCompressionFind (Integer csomópont) {DisjointSetInfo setInfo = nodes.get (csomópont); Egész szülő = setInfo.getParentNode (); if (szülő.egyenlő (csomópont)) {visszatér csomópont; } else {Egész szülőNode = keresés (szülő); setInfo.setParentNode (parentNode); return parentNode; }}

4.4. Uniós művelet

Ha egy él két csomópontja különböző halmazokban van, akkor ezt a két halmazt egyesítjük egybe. Ezt elérhetjük unió művelet úgy, hogy az egyik reprezentatív csomópont gyökerét beállítja a másik reprezentatív csomópontra:

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

Ez az egyszerű egyesítési művelet nagyon kiegyensúlyozatlan fát eredményezhet, mivel véletlenszerű gyökércsomópontot választottunk az egyesített halmazhoz. Javíthatjuk a teljesítményt az a használatával unió rang szerint technika.

Mivel a fa mélysége befolyásolja a megtalálja művelet, a rövidebb fával rendelkező halmazt a hosszabb fával rendelkező halmazhoz csatoljuk. Ez a technika csak akkor növeli az összevont fa mélységét, ha az eredeti két fa azonos mélységű.

Ennek elérése érdekében először a rang tulajdon a DisjointSetInfo osztály:

public class DisjointSetInfo {private Integer parentNode; magán int rang; DisjointSetInfo (Egész szülő) {setParentNode (szülő); setRank (0); } // szabványos beállítók és szerelők}

Kezdetben egyetlen csomópont diszjunkció rangja 0. Két halmaz egyesítése során a magasabb rangú gyökércsomópont az egyesített halmaz gyökércsomópontjává válik. Csak akkor növeljük az új gyökércsomópont rangját eggyel, ha az eredeti két rang megegyezik:

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. Ciklusérzékelés

Megállapíthatjuk, hogy két csomópont azonos diszjunkt halmazban van-e, összehasonlítva kettő eredményét megtalálja tevékenységek. Ha ugyanaz a reprezentatív gyökércsomópontjuk van, akkor észleltünk egy ciklust. Ellenkező esetben a két diszjunkt halmazt egyesítjük az a használatával unió művelet:

logikai detektálási ciklus (egész u, egész v) {egész gyökérU = pathCompressionFind (u); Egész gyök V = pathCompressionFind (v); if (rootU.egyenlő (rootV)) {true igaz; } unionByRank (rootU, rootV); return false; } 

A ciklus detektálása a unió rang szerint önmagában a technika, futási ideje: O (logV). Mindkettővel jobb teljesítményt érhetünk el útvonal tömörítés és unió rang szerint technikák. A futási idő O (α (V)), hol α (V) a csomópontok teljes számának inverz Ackermann-függvénye. Ez egy kicsi állandó, amely kevesebb, mint 5 a valós számítások során.

5. Kruskal’s Algorithm Java implementációja

Használhatjuk a ValueGraph adatstruktúra a Google Guava-ban, hogy egy éllel súlyozott grafikont ábrázoljon.

Használni ValueGraph, először hozzá kell adnunk a guavai függőséget a projektünkhöz pom.xml fájl:

     com.google.guava guava 28.1-jre 

A fenti ciklusérzékelési módszereket a-ba csomagolhatjuk CycleDetector osztályt, és használja Kruskal algoritmusában. Mivel a minimális és maximális átfedő fa felépítésének algoritmusai csak kis mértékben különböznek egymástól, egy általános függvényt használhatunk mindkét konstrukció elérésére:

ValueGraph spanningTree (ValueGraph gráf, logikai minSpanningTree) {Élek beállítása = graph.edges (); List edgeList = new ArrayList (élek); if (minSpanningTree) {edgeList.sort (Összehasonlító.összehasonlítás (e -> graph.edgeValue (e) .get ())); } else {edgeList.sort (Collections.reverseOrder (Comparator.comparing (e -> graph.edgeValue (e) .get ()))); } int totalNodes = graph.nodes (). size (); CycleDetector cycleDetector = új CycleDetector (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); mert (EndpointPair edge: edgeList) {if (cycleDetector.detectCycle (edge.nodeU (), edge.nodeV ())) {folytatás; } spanningTree.putEdgeValue (edge.nodeU (), edge.nodeV (), graph.edgeValue (edge) .get ()); edgeCount ++; if (edgeCount == totalNodes - 1) {törés; }} return spanningTree; }

Kruskal algoritmusában először az összes gráf élét súlyuk szerint rendezzük. Ez a művelet eltart O (ElogE) idő, hol E az élek száma.

Ezután egy hurkot használunk a rendezett éllista áttekintéséhez. Minden egyes iterációban ellenőrizzük, hogy létrejön-e ciklus az él hozzáadásával az aktuális átfogó fa élkészletbe. Ez a ciklus a ciklusészleléssel legfeljebb eltart O (ElogV) idő.

Ezért a teljes futási idő O (ELogE + ELogV). Mivel az értéke E skáláján van O (V2), Kruskal algoritmusának időbeli összetettsége O (ElogE) vagy O (ElogV).

6. Következtetés

Ebben a cikkben megtanultuk, hogyan használjuk Kruskal algoritmusát a grafikon minimális vagy maximális átfogó fájának megtalálásához. Mint mindig, a cikk forráskódja elérhető a GitHubon.