streamalism.org

1. Introduktion

I denne vejledning lærer vi først, hvad minimum træer er. Derefter bruger vi Prims algoritme til at finde en.

2. Minimum spændende træ

Et minimum spændende træ (MST) er en vægtet, ikke-rettet, forbundet graf, hvis samlede kantvægt er blevet minimeret ved at fjerne tungere kanter. Med andre ord holder vi alle hjørnerne i grafen intakte, men vi kan fjerne nogle kanter, så summen af ​​alle kanter er på et minimum.

Vi starter med en vægtet graf, da det ikke giver mening at minimere den samlede kantvægt, hvis disse kanter slet ikke har nogen vægt. Lad os se på et eksempel på en graf:

Ovenstående graf er en vægtet, ikke-rettet, forbundet graf. Her er en MST af denne graf:

En MST af en graf er dog ikke unik. Hvis en graf har mere end en MST, har hver MST den samme samlede kantvægt.

3. Prims algoritme

Prims algoritme tager en vægtet, ikke-rettet, forbundet graf som input og returnerer en MST af denne graf som output.

Det fungerer på en grådig måde. I det første trin vælger det et vilkårligt toppunkt. Derefter, hvert nye trin tilføjer det nærmeste toppunkt til det hidtil konstruerede træ indtil der ikke er noget afbrudt toppunkt tilbage.

Lad os køre Prims algoritme trin for trin på denne graf:

Forudsat at det vilkårlige toppunkt for at starte algoritmen er B, har vi tre valg A, C og E at gå. De tilsvarende vægte af kanterne er 2, 2 og 5, derfor er minimumet 2. I dette tilfælde har vi to kanter, der vejer 2, så vi kan vælge en af ​​dem (det betyder ikke noget hvilken). Lad os vælge A:

Nu har vi et træ med to hjørner A og B. Vi kan vælge en af ​​A- eller B-kanter, der endnu ikke er tilføjet, hvilket fører til et ikke-adresseret toppunkt. Så vi kan vælge AC, BC eller BE.

Prims algoritme vælger minimumet, som er 2 eller BC:

Nu har vi et træ med tre hjørner og tre mulige kanter til at bevæge sig fremad: CD, CE eller BE. AC er ikke inkluderet, da det ikke tilføjer et nyt toppunkt til træet. Minimumsvægten blandt disse tre er 1.

Der er dog to kanter, der begge vejer 1. Derfor vælger Prims algoritme en af ​​dem (igen betyder ikke noget hvilken) i dette trin:

Der er kun et toppunkt tilbage, så vi kan vælge mellem CE og BE. Den mindste vægt, der kan forbinde vores træ med det, er 1, og Prims algoritme vælger det:

Da alle hjørner af inputgrafen nu er til stede i outputtræet, slutter Prims algoritme. Derfor er dette træ en MST i inputgrafen.

4. Implementering

Højdepunkter og kanter laver grafer, så vi har brug for en datastruktur til at gemme disse elementer. Lad os oprette klassen Edge:

offentlig klasse Edge {privat int vægt; privat boolsk isIncluded = false; }

Hver Edge skal have en vægt da Prims algoritme fungerer på vægtede grafer. erInkluderet viser, om Edge er til stede i det mindst spændende træ eller ej.

Lad os nu tilføje Hvirvel klasse:

public class Vertex {private String label = null; private kortkanter = ny HashMap (); privat boolsk isVisited = false; }

Hver Hvirvel kan valgfrit have en etiket. Vi bruger kanter kort for at gemme forbindelser mellem hjørner. Langt om længe, isVisited viser, om toppunktet hidtil er blevet besøgt af Prims algoritme eller ej.

Lad os skabe vores Prim klasse, hvor vi implementerer logikken:

offentlig klasse Prim {privat liste graf; }

En liste over hjørner er nok til at gemme hele grafen, fordi inde i hver Hvirvel, vi har en Kort for at identificere alle forbindelser. Inde Prim, vi skaber en løb() metode:

public void run () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } mens (isDisconnected ()) {Edge nextMinimum = ny Edge (Integer.MAX_VALUE); Vertex nextVertex = graph.get (0); for (Vertex toppunkt: graf) {if (vertex.isVisited ()) {Par kandidat = vertex.nextMinimum (); hvis (candid.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = kandidat.getValue (); nextVertex = kandidat.getKey (); }}} nextMinimum.setIncluded (true); nextVertex.setVisited (true); }}

Vi starter med at indstille det første element i Liste graf som besøgt. Det første element kan være en hvilken som helst af hjørnerne afhængigt af rækkefølgen, de er blevet føjet til listen i første omgang. isDisconnected () vender tilbage rigtigt hvis der er nogen Hvirvel ikke besøgt hidtil:

privat boolsk isDisconnected () {for (Vertex toppunkt: graf) {hvis (! vertex.isVisited ()) {return sand; }} returner falsk; }

Mens det mindste spændende træ isDisconnected (), løber vi over de allerede besøgte hjørner og finder Edge med den mindste vægt som kandidat til næsteVertex:

public Pair nextMinimum () {Edge nextMinimum = new Edge (Integer.MAX_VALUE); Vertex nextVertex = dette; Iterator it = kanter.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 (); }}}} returner nyt par (nextVertex, nextMinimum); }

Vi finder minimum af alle kandidats i hovedsløjfen, og opbevar den i næsteVertex. Så satte vi os af næsteVertex som besøgt. Loop fortsætter, indtil alle hjørner er besøgt.

I slutningen, hver Edge med erInkluderet svarende til rigtigt er til stede.

Bemærk, at siden næsteMinimum () det gentager sig gennem kanterne, tidskompleksiteten af ​​denne implementering er O (V2). Hvis vi gemmer kanterne i en prioritetskø (sorteret efter vægt) i stedet, udføres algoritmen i O (E log V).

5. Testning

Okay, så nu hvor vi har noget kode, lad os teste det med et rigtigt eksempel. Først konstruerer vi vores graf:

offentlig statisk liste createGraph () {Liste graf = ny ArrayList (); Vertex a = ny Vertex ("A"); ... Vertex e = ny Vertex ("E"); Edge ab = ny Edge (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = ny Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... graf. tilføj (e); retur graf; }

Konstruktøren af Prim klasse tager det og gemmer det inde i klassen. Vi kan udskrive inputgrafen med originalGraphToString () metode:

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

Vores eksempel vil output:

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

Nu kører vi Prims algoritme og udskriver den resulterende MST med minimumSpanningTreeToString () metode:

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

Endelig udskriver vi vores MST:

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

6. Konklusion

I denne artikel lærte vi, hvordan Prims algoritme finder et minimum spændende træ i en graf. Koden er tilgængelig på GitHub.