streamalism.org

1. Inleiding

In deze tutorial leren we eerst wat minimaal opspannende bomen zijn. Daarna gebruiken we het algoritme van Prim om er een te vinden.

2. Minimale overspanningsboom

Een minimum spanning tree (MST) is een gewogen, ongerichte, verbonden graaf waarvan het totale randgewicht is geminimaliseerd door zwaardere randen te verwijderen. Met andere woorden, we houden alle hoekpunten van de grafiek intact, maar we kunnen enkele randen verwijderen zodat de som van alle randen minimaal is.

We beginnen met een gewogen grafiek, omdat het geen zin heeft om het totale randgewicht te minimaliseren als die randen helemaal geen gewicht hebben. Laten we een voorbeeldgrafiek bekijken:

De bovenstaande grafiek is een gewogen, ongerichte, verbonden grafiek. Hier is een MST van die grafiek:

Een MST van een grafiek is echter niet uniek. Als een grafiek meer dan één MST heeft, heeft elke MST hetzelfde totale randgewicht.

3. Prim's algoritme

Het algoritme van Prim neemt een gewogen, ongerichte, verbonden grafiek als invoer en retourneert een MST van die grafiek als uitvoer.

Het werkt op een hebzuchtige manier. In de eerste stap selecteert het een willekeurig hoekpunt. Daarna, elke nieuwe stap voegt het dichtstbijzijnde hoekpunt toe aan de tot dusver geconstrueerde boom totdat er geen losgekoppeld hoekpunt meer over is.

Laten we het algoritme van Prim stap voor stap in deze grafiek uitvoeren:

Ervan uitgaande dat het willekeurige hoekpunt om het algoritme te starten B is, hebben we drie keuzes A, C en E te gaan. De overeenkomstige gewichten van de randen zijn 2, 2 en 5, daarom is het minimum 2. In dit geval hebben we twee randen die 2 wegen, dus we kunnen een van beide kiezen (het maakt niet uit welke). Laten we A kiezen:

Nu hebben we een boom met twee hoekpunten A en B. We kunnen elke rand van A of B selecteren die nog niet is toegevoegd en die naar een niet-toegevoegd hoekpunt leidt. We kunnen dus AC, BC of BE kiezen.

Het algoritme van Prim kiest het minimum, namelijk 2, of BC:

Nu hebben we een boom met drie hoekpunten en drie mogelijke randen om vooruit te gaan: CD, CE of BE. AC is niet opgenomen omdat het geen nieuw hoekpunt aan de boom zou toevoegen. Het minimumgewicht van deze drie is 1.

Er zijn echter twee kanten die beide 1 wegen. Daarom kiest het algoritme van Prim er een uit (ook hier maakt het niet uit welke) in deze stap:

Er is nog maar één hoekpunt om samen te voegen, dus we kunnen kiezen uit CE en BE. Het minimumgewicht dat onze boom ermee kan verbinden, is 1, en het algoritme van Prim zal het kiezen:

Aangezien alle hoekpunten van de invoergrafiek nu aanwezig zijn in de uitvoerboom, eindigt het algoritme van Prim. Daarom is deze boom een ​​MST van de invoergrafiek.

4. Implementatie

Hoekpunten en randen maken grafieken, dus we hebben een datastructuur nodig om deze elementen op te slaan. Laten we de klas maken Rand:

openbare klasse Edge {privé int gewicht; private boolean isIncluded = false; }

Elk Rand moet een gewicht omdat het algoritme van Prim werkt op gewogen grafieken. inbegrepen laat zien of het Rand is aanwezig in de minimum spanning tree of niet.

Laten we nu het Vertex klasse:

openbare klasse Vertex {private String label = null; privékaartranden = nieuwe HashMap (); private boolean isVisited = false; }

Elk Vertex kan optioneel een etiket. Wij gebruiken de randen map om verbindingen tussen hoekpunten op te slaan. Tenslotte, wordt bezocht laat zien of het hoekpunt tot nu toe is bezocht door het algoritme van Prim of niet.

Laten we onze Prim klasse waar we de logica implementeren:

openbare klasse Prim {privélijstgrafiek; }

Een lijst met hoekpunten is voldoende om de hele grafiek op te slaan, want binnen elk Vertex, we hebben een Kaart om alle verbindingen te identificeren. Binnen Prim, we creëren een rennen() methode:

public void run () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } while (isDisconnected ()) {Edge nextMinimum = nieuwe Edge (Integer.MAX_VALUE); Vertex 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); }}

We beginnen met het instellen van het eerste element van de Lijst met grafiek zoals bezocht. Het eerste element kan elk van de hoekpunten zijn, afhankelijk van de volgorde waarin ze in de eerste plaats aan de lijst zijn toegevoegd. isDisconnected () geeft terug waar als er iets is Vertex tot nu toe niet bezocht:

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

Terwijl de minimum spanning tree isDisconnected (), we doorlopen de reeds bezochte hoekpunten en vinden de Rand met het minimumgewicht als kandidaat voor volgendeVertex:

openbaar paar nextMinimum () {Edge nextMinimum = nieuwe Edge (Integer.MAX_VALUE); Vertex nextVertex = dit; Iterator it = randen.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 = paar .getValue (); nextVertex = pair.getKey (); }}}} retourneer nieuw paar (nextVertex, nextMinimum); }

We vinden het minimum van alles kandidaats in de hoofdlus en sla deze op in volgendeVertex. Dan gaan we volgendeVertex zoals bezocht. De lus gaat door totdat alle hoekpunten zijn bezocht.

Op het eind, elk Rand met inbegrepen gelijk aan waar is aanwezig.

Merk op dat sinds volgendeMinimum () itereert door de randen, de tijdcomplexiteit van deze implementatie is O (V2). Als we de randen in plaats daarvan opslaan in een prioriteitswachtrij (gesorteerd op gewicht), zal het algoritme presteren in O (E log V).

5. Testen

Oké, dus nu we wat code hebben, laten we het testen met een echt voorbeeld. Eerst construeren we onze grafiek:

openbare statische lijst createGraph () {Lijstgrafiek = nieuwe ArrayList (); Vertex a = nieuw Vertex ("A"); ... Vertex e = nieuw Vertex ("E"); Edge ab = nieuwe Edge (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = nieuwe Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... graph.add (e); terugkeer grafiek; }

De constructeur van het Prim class pakt het en slaat het op in de klas. We kunnen de invoergrafiek afdrukken met originalGraphToString () methode:

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

Ons voorbeeld levert het volgende op:

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

Nu draaien we het algoritme van Prim en drukken we de resulterende MST af met minimumSpanningTreeToString () methode:

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

Ten slotte printen we onze MST:

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

6. Conclusie

In dit artikel hebben we geleerd hoe het algoritme van Prim een ​​minimale spanning tree van een graaf vindt. De code is beschikbaar op GitHub.