streamalism.org

1. Uvod

U ovom uputstvu prvo saznajemo što su minimalna rasprostranjena stabla. Poslije ćemo koristiti Primov algoritam da bismo ga pronašli.

2. Minimalno rastezno drvo

Stablo minimalnog raspona (MST) ponderirani je, neusmjereni, povezani graf čija je ukupna težina ruba umanjena uklanjanjem težih rubova. Drugim riječima, držimo sve vrhove grafa netaknutima, ali neke rubove možemo ukloniti tako da zbroj svih bridova bude minimalan.

Počinjemo s ponderiranim grafom jer nema smisla minimizirati ukupnu težinu ruba ako ti rubovi uopće nemaju težinu. Pogledajmo primjer grafa:

Gornji graf je ponderirani, neusmjereni, povezani graf. Evo MST-a tog grafa:

MST grafa ipak nije jedinstven. Ako graf ima više od jednog MST-a, tada svaki MST ima istu ukupnu težinu ruba.

3. Primov algoritam

Primov algoritam uzima ponderirani, neusmjereni, povezani graf kao ulaz i vraća MST tog grafa kao izlaz.

Djeluje na pohlepan način. U prvom koraku odabire proizvoljan vrh. Nakon, svaki novi korak dodaje najbliži vrh do sada izgrađenom stablu sve dok ne ostane nepovezani vrh.

Pokrenimo Primov algoritam na ovom grafu korak po korak:

Pod pretpostavkom da je proizvoljni vrh za pokretanje algoritma B, imamo tri izbora A, C i E. Odgovarajuće težine bridova su 2, 2 i 5, dakle minimum je 2. U ovom slučaju imamo dva ruba težine 2, pa možemo odabrati bilo koji od njih (nije važno koji). Odaberite A:

Sada imamo stablo s dva vrha A i B. Možemo odabrati bilo koji od A ili B rubova koji još nisu dodani i koji vode do neupadanog vrha. Dakle, možemo odabrati AC, BC ili BE.

Primov algoritam bira minimum, a to je 2 ili BC:

Sada imamo stablo s tri vrha i tri moguća ruba za pomicanje naprijed: CD, CE ili BE. AC nije uključen jer ne bi dodao novi vrh na stablo. Minimalna težina između ove tri je 1.

Međutim, postoje dva ruba koji teže jedan 1. Prema tome, Primov algoritam u ovom koraku bira jedan od njih (opet nije važno koji):

Preostao je još samo jedan vrh za pridruživanje, pa možemo birati između CE i BE. Minimalna težina koja može povezati naše stablo s njom je 1, a Primov algoritam će je odabrati:

Kako su svi vrhovi ulaznog grafa sada prisutni u izlaznom stablu, Primov algoritam završava. Stoga je ovo stablo MST ulaznog grafa.

4. Provedba

Vrhovi i rubovi čine grafikone, pa nam je potrebna struktura podataka za pohranu tih elemenata. Stvorimo razred Rub:

javna klasa Edge {private int weight; private boolean isIncluded = false; }

Svaki Rub mora imati a težina budući da Primov algoritam radi na ponderiranim grafovima. jeUključeno pokazuje da li Rub je prisutan u minimalnom rasponu stabla ili ne.

Dodajmo sada Vrh razred:

javna klasa Vertex {private String label = null; rubovi privatne karte = novi HashMap (); privatni logički isVisited = false; }

Svaki Vrh po želji može imati a označiti. Koristimo rubovi karta za pohranu veza među vrhovima. Konačno, isVisited pokazuje je li vrh dosad posjetio Primov algoritam ili nije.

Stvorimo svoje Prim klase u kojoj ćemo implementirati logiku:

javni razred Prim {graf privatnog popisa; }

Popis vrhova dovoljan je za spremanje cijelog grafa jer se unutar svakog Vrh, imamo Karta identificirati sve veze. Iznutra Prim, mi stvaramo a trčanje() metoda:

public void run () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } while (isDisconnected ()) {Edge nextMinimum = new Edge (Integer.MAX_VALUE); Vrh nextVertex = graph.get (0); za (Vertex vertex: graf) {if (vertex.isVisited ()) {Par kandidata = vertex.nextMinimum (); if (kandidat.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = kandidat.getValue (); nextVertex = kandidat.getKey (); }}} nextMinimum.setIncluded (true); nextVertex.setVisited (true); }}

Počinjemo postavljanjem prvog elementa Grafikon popisa kao posjećen. Prvi element može biti bilo koji od vrhova, ovisno o redoslijedu na kojem su uopće dodani na popis. isDisconnected () vraća se pravi ako ih ima Vrh do sada nije posjećeno:

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

Dok je minimalno rasponično stablo isDisconnected (), petljamo po već posjećenim vrhovima i pronalazimo Rub s minimalnom težinom kao kandidat za nextVertex:

javni par nextMinimum () {Edge nextMinimum = novi Edge (Integer.MAX_VALUE); Vertex nextVertex = ovo; Iterator it = rubovi.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 = pair .getValue (); nextVertex = pair.getKey (); }}}} vrati novi par (nextVertex, nextMinimum); }

Pronalazimo minimum svega kandidats u glavnoj petlji i spremite je u nextVertex. Zatim smo postavili nextVertex kao posjećen. Petlja traje sve dok se ne posjete svi vrhovi.

Na kraju, svaki Rub s jeUključeno jednak pravi je prisutan.

Imajte na umu da od nextMinimum () ponavlja kroz rubove, vremenska složenost ove provedbe je O (V2). Ako umjesto toga rubove pohranimo u prioritetni red (poredane po težini), algoritam će izvesti u O (E log V).

5. Ispitivanje

Ok, sad kad imamo neki kôd, testirajmo ga na stvarnom primjeru. Prvo, konstruiramo naš graf:

javni statički popis createGraph () {Grafikon popisa = novi ArrayList (); Vrh a = novi vrh ("A"); ... Vrh e = novi vrh ("E"); Rub ab = novi rub (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = novi Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... graph.add (e); graf povratka; }

Konstruktor Prim razred uzima i sprema u razred. Ulazni graf možemo ispisati pomoću originalGraphToString () metoda:

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

Naš će primjer dati:

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

Sada pokrećemo Primov algoritam i ispisujemo rezultirajući MST minimumSpanningTreeToString () metoda:

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

Na kraju, ispisujemo naš MST:

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

6. Zaključak

U ovom smo članku saznali kako Primov algoritam pronalazi minimalno rasponično stablo grafa. Kôd je dostupan na GitHub-u.