streamalism.org

1. Úvod

V tomto tutoriáli sa najskôr dozvieme, čo sú minimálne rozložené stromy. Potom použijeme Primov algoritmus, aby sme ho našli.

2. Minimálny rozpätie stromu

Minimálny rozpätie stromu (MST) je vážený, neusmernený a prepojený graf, ktorého celková váha hrán bola minimalizovaná odstránením ťažších hrán.. Inými slovami, ponecháme všetky vrcholy grafu neporušené, ale môžeme niektoré okraje odstrániť, aby bol súčet všetkých okrajov minimálny.

Začneme váženým grafom, pretože nemá zmysel minimalizovať celkovú váhu hrán, ak tieto hrany nemajú vôbec žiadnu váhu. Pozrime sa na príklad grafu:

Vyššie uvedený graf je vážený, neusmernený a prepojený graf. Tu je MST tohto grafu:

MST grafu však nie je jedinečný. Ak má graf viac ako jeden MST, potom má každý MST rovnakú celkovú hmotnosť okraja.

3. Primov algoritmus

Primov algoritmus vezme vážený, neusmernený a pripojený graf ako vstup a vráti MST tohto grafu ako výstup.

Funguje to chamtivo. V prvom kroku vyberie ľubovoľný vrchol. Potom, každý nový krok pridá najbližší vrchol k doteraz zostrojenému stromu kým nezostane odpojený vrchol.

Spustime Primov algoritmus na tomto grafe krok za krokom:

Za predpokladu, že ľubovoľný vrchol na spustenie algoritmu je B, máme pred sebou tri možnosti A, C a E. Zodpovedajúce hmotnosti okrajov sú 2, 2 a 5, preto je minimum 2. V tomto prípade máme dve hrany s hmotnosťou 2, takže si môžeme zvoliť ktorúkoľvek z nich (nezáleží na tom, ktorá z nich). Vyberme A:

Teraz máme strom s dvoma vrcholmi A a B. Môžeme zvoliť ľubovoľný z zatiaľ nepridaných okrajov A alebo B, ktoré vedú k nepridanému vrcholu. Môžeme teda zvoliť AC, BC alebo BE.

Primov algoritmus vyberie minimum, ktoré je 2 alebo BC:

Teraz máme strom s tromi vrcholmi a tromi možnými hranami, ktoré sa dajú posunúť vpred: CD, CE alebo BE. AC nie je zahrnutý, pretože by do stromu nepridal nový vrchol. Minimálna hmotnosť medzi týmito tromi je 1.

Avšak existujú dve hrany, ktoré vážia 1. V dôsledku toho Primov algoritmus v tomto kroku vyberie jednu z nich (opäť nezáleží na tom, ktorá z nich):

Na pripojenie zostáva len jeden vrchol, takže môžeme zvoliť z CE a BE. Minimálna hmotnosť, ktorá k nemu môže pripojiť náš strom, je 1 a Primov algoritmus ju vyberie:

Pretože všetky vrcholy vstupného grafu sú teraz prítomné vo výstupnom strome, Primov algoritmus končí. Preto je tento strom MST vstupného grafu.

4. Implementácia

Vrcholy a hrany vytvárajú grafy, takže na ukladanie týchto prvkov potrebujeme dátovú štruktúru. Vytvorme triedu Hrana:

public class Edge {private int weight; private boolean isIncluded = false; }

Každý Hrana musí mať a váha pretože Primov algoritmus pracuje na vážených grafoch. je Zahrnuté ukazuje, či Hrana je prítomný v strome s minimálnym rozpätím alebo nie.

Teraz pridajme Vrchol trieda:

verejná trieda Vertex {private String label = null; privátne okraje mapy = nový HashMap (); private boolean isVisited = false; }

Každý Vrchol môže voliteľne mať a štítok. Používame hrany mapa na ukladanie spojení medzi vrcholmi. Nakoniec je navštívený ukazuje, či vrchol bol doteraz navštívený Primovým algoritmom alebo nie.

Poďme vytvoriť naše Prim triedy, kde implementujeme logiku:

public class Prim {private List graph; }

Zoznam vrcholov je dostatočný na uloženie celého grafu, pretože vnútri každého Vrchol, máme Mapa na identifikáciu všetkých spojení. Vo vnútri Prim, tvoríme a run () metóda:

public void run () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } while (isDisconnected ()) {Edge nextMinimum = new Edge (Integer.MAX_VALUE); Vrchol nextVertex = graph.get (0); for (Vertex vertex: graph) {if (vertex.isVisited ()) {Pair candidate = vertex.nextMinimum (); if (candidate.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = candidate.getValue (); nextVertex = candidate.getKey (); }}} nextMinimum.setIncluded (true); nextVertex.setVisited (true); }}

Začneme nastavením prvého prvku súboru Uveďte graf ako navštívil. Prvým prvkom môže byť ktorýkoľvek z vrcholov v závislosti od poradia, v akom boli pridané do zoznamu. je odpojené () vracia pravda ak nejaké existujú Vrchol zatiaľ nenavštívené:

private boolean isDisconnected () {for (Vertex vertex: graph) {if (! vertex.isVisited ()) {return true; }} return false; }

Zatiaľ čo minimálny kostra je odpojené (), prehrnieme sa nad už navštívenými vrcholmi a nájdeme Hrana s minimálnou hmotnosťou ako kandidát na nextVertex:

public Pair nextMinimum () {Edge nextMinimum = nový Edge (Integer.MAX_VALUE); Vertex nextVertex = this; Iterátor it = edge.entrySet () .iterator (); while (it.hasNext ()) {Map.Entry pair = it.next (); if (! pair.getKey (). isVisited ()) {if (! pair.getValue (). isIncluded ()) {if (pair.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = pár .getValue (); nextVertex = pair.getKey (); }}}} vrátiť nový pár (nextVertex, nextMinimum); }

Nájdeme minimum všetkých kandidáts v hlavnej slučke a uložte ju do nextVertex. Potom sme nastavili nextVertex ako navštívil. Smyčka pokračuje, kým nenavštívite všetky vrcholy.

Nakoniec, každý Hrana s je Zahrnuté rovná pravda je prítomný.

Všimnite si, že od nextMinimum () iteruje cez okraje, časová zložitosť tejto implementácie je O (V2). Ak namiesto toho uložíme hrany do prioritného radu (zoradené podľa hmotnosti), bude algoritmus fungovať v O (E log V).

5. Testovanie

Dobre, takže teraz, keď máme nejaký kód, otestujme ho na skutočnom príklade. Najskôr zostrojíme náš graf:

public static List createGraph () {List graph = new ArrayList (); Vrchol a = nový vrchol ("A"); ... Vrchol e = nový Vrchol ("E"); Edge ab = nový Edge (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = nový Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... graph.add (e); návratový graf; }

Konštruktér spoločnosti Prim trieda to vezme a uloží do triedy. Vstupný graf môžeme vytlačiť pomocou originalGraphToString () metóda:

Prim prim = nový Prim (createGraph ()); System.out.println (prim.originalGraphToString ());

Náš príklad bude mať výstup:

A --- 2 --- B A --- 3 --- C B --- 5 --- E B --- 2 --- C C --- 1 --- E C --- 1 --- D

Teraz spustíme Primov algoritmus a vytlačíme výsledný MST pomocou minimumSpanningTreeToString () metóda:

prim.run (); prim.resetPrintHistory (); System.out.println (prim.minimumSpanningTreeToString ());

Na záver vytlačíme náš MST:

A --- 2 --- B B --- 2 --- C C --- 1 --- E C --- 1 --- D

6. Záver

V tomto článku sme sa dozvedeli, ako Primov algoritmus nájde minimálny spanningový strom grafu. Kód je k dispozícii na GitHub.