streamalism.org

1. Pregled

U prethodnom članku predstavili smo Primov algoritam za pronalaženje minimalnog raspona stabala. U ovom ćemo članku koristiti drugi pristup, Kruskalov algoritam, za rješavanje problema s minimalnim i maksimalnim obuhvaćajućim stablom.

2. Rasprostiruće se drvo

Rasprostranjeno stablo neusmjerenog grafa povezan je podgraf koji pokriva sve čvorove grafa s najmanjim mogućim brojem bridova. Općenito, graf može imati više od jednog raspona stabla. Sljedeća slika prikazuje graf s rastegljivim stablom (rubovi rasprostranjenog stabla su crvene boje):

Ako je graf ponderiran rubovima, težinu rastegnutog stabla možemo definirati kao zbroj težina svih njegovih bridova. Minimalno rašireno stablo je rastuće stablo čija je težina najmanja među svim mogućim drvećima. Sljedeća slika prikazuje stablo minimalnog raspona na grafu ponderiranom rubom:

Slično tome, stablo s najvećim rasponom ima najveću težinu među svim rasponima. Sljedeća slika prikazuje stablo maksimalnog raspona na grafu ponderiranom rubom:

3. Kruskalov algoritam

S obzirom na graf, pomoću Kruskalovog algoritma možemo pronaći njegovo minimalno rasponično stablo. Ako je broj čvorova u grafu V, tada bi svako njegovo drveće koje se proteže trebalo imati rubove (V-1) i ne bi trebalo sadržavati cikluse. Kruskalov algoritam možemo opisati u sljedećem pseudo-kodu:

Inicijalizirajte prazan skup bridova T. Razvrstajte sve rubove grafa rastućim redoslijedom njihovih vrijednosti težine. rub svakog ruba na sortiranom popisu rubova Provjerite hoće li stvoriti ciklus s rubovima unutar T. Ako rub ne uvodi nijedan ciklus, dodajte ga u T. Ako T ima (V-1) rubove, izađite iz petlje. povratak T

Pokrenimo Kruskalov algoritam za minimalno obuhvatno stablo na našem uzorku grafikona korak po korak:

Prvo, biramo rub (0, 2) jer ima najmanju težinu. Zatim možemo dodati rubove (3, 4) i (0, 1) jer oni ne stvaraju nikakve cikluse. Sada je sljedeći kandidat rub (1, 2) s težinom 9. Međutim, ako uključimo ovaj rub, proizvest ćemo ciklus (0, 1, 2). Stoga odbacujemo ovaj rub i nastavljamo odabrati sljedeći najmanji. Konačno, algoritam se završava dodavanjem ruba (2, 4) utega 10.

Da bismo izračunali maksimalno rasponsko stablo, možemo promijeniti redoslijed sortiranja u silazni. Ostali koraci ostaju isti. Sljedeća slika prikazuje korak-po-korak konstrukciju stabla s maksimalnim rasponom na našem uzorku grafikona.

4. Otkrivanje ciklusa s disjontnim skupom

U Kruskalovom algoritmu presudni je dio provjeriti hoće li rub stvoriti ciklus ako ga dodamo postojećem skupu rubova. Postoji nekoliko algoritama za otkrivanje ciklusa grafova koje možemo koristiti. Na primjer, možemo koristiti algoritam dubinskog pretraživanja (DFS) da bismo prešli graf i otkrili postoji li ciklus.

Međutim, svaki put kada testiramo novi rub moramo izvršiti otkrivanje ciklusa na postojećim rubovima. Brže rješenje je uporaba algoritma Union-Find s disjunktnom strukturom podataka jer i onkoristi pristup inkrementalnog dodavanja ruba za otkrivanje ciklusa. To možemo uklopiti u naš postupak gradnje stabala.

4.1. Konstrukcija disjontnih skupova i rasprostranjenih stabala

Prvo, svaki čvor grafikona tretiramo kao pojedinačni skup koji sadrži samo jedan čvor. Zatim, svaki put kad uvedemo rub, provjeravamo jesu li njegova dva čvora u istom skupu. Ako je odgovor da, tada će stvoriti ciklus. U suprotnom, spajamo dva nepodudarna skupa u jedan skup i uključujemo rub za rasprostiruće se stablo.

Gornje korake možemo ponavljati dok ne konstruiramo cijelo stablo koje se proteže.

Na primjer, u gornjoj minimalnoj konstrukciji stabla koja obuhvaća, prvo imamo 5 skupova čvorova: {0}, {1}, {2}, {3}, {4}. Kada provjerimo prvi rub (0, 2), njegova dva čvora nalaze se u različitim skupovima čvorova. Stoga možemo uključiti ovaj rub i spojiti {0} i {2} u jedan skup {0, 2}.

Možemo raditi slične operacije za rubove (3, 4) i (0, 1). Skupovi čvorova tada postaju {0, 1, 2} i {3, 4}. Kada provjerimo sljedeći rub (1, 2), možemo vidjeti da su oba čvora tog ruba u istom skupu. Stoga odbacujemo ovaj rub i nastavljamo provjeravati sljedeći. Konačno, rub (2, 4) zadovoljava naše stanje i možemo ga uključiti za minimalno rasponično stablo.

4.2. Provedba disjontnog skupa

Strukturu stabla možemo koristiti za predstavljanje disjunktnog skupa. Svaki čvor ima roditelj pokazivač na referencu svog nadređenog čvora. U svakom skupu postoji jedinstveni korijenski čvor koji predstavlja taj skup. Korijenski čvor ima samo-referencu roditelj pokazivač.

Upotrijebimo Java klasu za definiranje podataka o disjontnom skupu:

javna klasa DisjointSetInfo {private Integer parentNode; DisjointSetInfo (Integer roditelj) {setParentNode (roditelj); } // standardni postavljači i dobivači}

Označimo svaki čvor grafa cjelobrojnim brojem, počevši od 0. Možemo koristiti strukturu podataka popisa, Popis čvorova, za pohranu podataka o disjontnom skupu grafa. Na početku je svaki čvor reprezentativni član vlastitog skupa:

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

4.3. Pronađi operaciju

Da bismo pronašli skup kojem pripada čvor, možemo pratiti roditeljski lanac čvora prema gore dok ne dođemo do korijenskog čvora:

Cjelovito pronalaženje (cjelobrojni čvor) {Integer roditelj = nodes.get (node) .getParentNode (); if (nadređeni.equals (čvor)) {return čvor; } else {return find (nadređeni); }}

Moguće je imati vrlo neuravnoteženu strukturu stabla za disjontni skup. Možemo poboljšati pronaći rad pomoću strkompresija tehnika.

Budući da je svaki čvor koji posjetimo na putu do korijenskog čvora dio istog skupa, korijenski čvor možemo priložiti njegovom roditelj referenca izravno. Sljedeći put kada posjetimo ovaj čvor, potreban nam je jedan put pretraživanja da bismo dobili korijenski čvor:

Integer pathCompressionFind (Integer čvor) {DisjointSetInfo setInfo = nodes.get (čvor); Cijeli roditelj = setInfo.getParentNode (); if (nadređeni.equals (čvor)) {return čvor; } else {Integer nadređeni čvor = find (nadređeni); setInfo.setParentNode (nadređeni čvor); return parentNode; }}

4.4. Sindikalna operacija

Ako su dva čvora brida u različitim skupovima, kombinirat ćemo ta dva skupa u jedan. To možemo postići unija operacija postavljanjem korijena jednog reprezentativnog čvora drugom reprezentativnom čvoru:

uništenje praznina (Integer rootU, Integer rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); setInfoU.setParentNode (rootV); }

Ova jednostavna operacija spajanja mogla bi stvoriti vrlo neuravnoteženo stablo jer smo za spojeni skup odabrali slučajni korijenski čvor. Izvedbu možemo poboljšati pomoću a sindikat po rangu tehnika.

Budući da dubina stabla utječe na vrijeme rada pronaći operacija, pričvršćujemo set s kraćim stablom na set s dužim stablom. Ova tehnika povećava dubinu spojenog stabla samo ako izvorna dva stabla imaju istu dubinu.

Da bismo to postigli, prvo dodamo a rang vlasništvo na DisjointSetInfo razred:

javna klasa DisjointSetInfo {private Integer parentNode; privatni int čin; DisjointSetInfo (Integer roditelj) {setParentNode (roditelj); setRank (0); } // standardni postavljači i dobivači}

U početku disjuint jednog čvora ima rang 0. Tijekom spajanja dva skupa, korijenski čvor višeg ranga postaje korijenski čvor spojenog skupa. Rang novog korijenskog čvora povećavamo za jedan samo ako su originalna dva ranga ista:

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. Otkrivanje ciklusa

Usporedbom rezultata dva možemo utvrditi jesu li dva čvora u istom disjontnom skupu pronaći operacijama. Ako imaju isti reprezentativni korijenski čvor, tada smo otkrili ciklus. U suprotnom, spajamo dva disjunktna ​​skupa pomoću a unija operacija:

boolean identifyCycle (Integer u, Integer v) {Integer rootU = pathCompressionFind (u); Cijeli korijenV = pathCompressionFind (v); if (rootU.equals (rootV)) {return true; } unionByRank (rootU, rootV); return false; } 

Detekcija ciklusa, sa sindikat po rangu sama tehnika, ima vrijeme izvođenja O (logV). Oboje možemo postići bolje performanse kompresija puta i sindikat po rangu Tehnike. Vrijeme izvođenja je O (α (V)), gdje α (V) je inverzna Ackermannova funkcija ukupnog broja čvorova. To je mala konstanta koja je manja od 5 u našim stvarnim proračunima.

5. Java implementacija Kruskalovog algoritma

Možemo koristiti ValueGraph struktura podataka u Google Guavi za predstavljanje grafa ponderiranog s rubom.

Koristiti ValueGraph, prvo moramo dodati ovisnost o Guavi na naš projekt pom.xml datoteka:

     com.google.guava guava 28,1-jre 

Gore navedene metode otkrivanja ciklusa možemo umotati u Detektor ciklusa klase i koristiti ga u Kruskalovu algoritmu. Budući da minimalni i maksimalni algoritmi za građenje stabla imaju samo malu razliku, možemo koristiti jednu opću funkciju za postizanje obje konstrukcije:

ValueGraph spanningTree (ValueGraph graf, logički minSpanningTree) {Postavi rubove = graph.edges (); Popis edgeList = novi ArrayList (rubovi); 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 = novi CycleDetector (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); za (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; }} povratak spanningTree; }

U Kruskalovom algoritmu prvo razvrstavamo sve rubove grafova po težini. Ova operacija traje O (ElogE) vrijeme, gdje E je ukupan broj bridova.

Zatim koristimo petlju za prolazak kroz sortirani popis rubova. U svakoj iteraciji provjeravamo hoće li se oblikovati ciklus dodavanjem ruba u trenutni skup bridova stabla koji se proteže. Ova petlja s otkrivanjem ciklusa traje najviše O (ElogV) vrijeme.

Stoga je ukupno vrijeme rada O (ELogE + ELogV). Budući da je vrijednost E je u mjerilu O (V2), vremenska složenost Kruskalovog algoritma je O (ElogE) ili O (ElogV).

6. Zaključak

U ovom smo članku naučili kako koristiti Kruskalov algoritam za pronalaženje minimalnog ili maksimalnog raspona stabla grafa. Kao i uvijek, izvorni kôd članka dostupan je na GitHubu.