streamalism.org

1. Introduksjon

I denne opplæringen lærer vi først hva som er minst spennende trær. Etterpå bruker vi Prims algoritme for å finne en.

2. Minimum spennende tre

Et minimumstreet (MST) er en vektet, ikke-rettet, tilkoblet graf hvis totale kantvekt er minimert ved å fjerne tyngre kanter.. Med andre ord holder vi alle hjørnene i grafen intakte, men vi kan fjerne noen kanter slik at summen av alle kantene er på et minimum.

Vi starter med en vektet graf siden det ikke gir mening å minimere den totale kantvekten hvis disse kantene ikke har noen vekt i det hele tatt. La oss ta en titt på et eksempel på en graf:

Ovenstående graf er en vektet, ikke-rettet, sammenhengende graf. Her er en MST av grafen:

En MST av en graf er imidlertid ikke unik. Hvis en graf har mer enn en MST, har hver MST samme totale kantvekt.

3. Prims algoritme

Prims algoritme tar en vektet, ikke-rettet, tilkoblet graf som inngang og returnerer en MST av den grafen som utdata.

Det fungerer på en grådig måte. I det første trinnet velger den et vilkårlig toppunkt. Deretter, hvert nye trinn legger til nærmeste toppunkt til treet som er konstruert så langt til det ikke er noe frakoblet toppunkt igjen.

La oss kjøre Prims algoritme trinnvis for denne grafen:

Forutsatt at det vilkårlige toppunktet for å starte algoritmen er B, har vi tre valg A, C og E å gå. De tilsvarende vektene til kantene er 2, 2 og 5, derfor er minimum 2. I dette tilfellet har vi to kanter som veier 2, så vi kan velge en av dem (det spiller ingen rolle hvilken). La oss velge A:

Nå har vi et tre med to hjørner A og B. Vi kan velge hvilken som helst av A- eller B-kantene som ennå ikke er lagt til, og som fører til et ikke-adressert toppunkt. Så vi kan velge AC, BC eller BE.

Prims algoritme velger minimum, som er 2, eller BC:

Nå har vi et tre med tre hjørner og tre mulige kanter å bevege oss fremover: CD, CE eller BE. AC er ikke inkludert siden det ikke vil legge et nytt toppunkt til treet. Minimumsvekten blant disse tre er 1.

Imidlertid er det to kanter som begge veier 1. Derfor velger Prims algoritme en av dem (igjen spiller ingen rolle hvilken) i dette trinnet:

Det er bare ett toppunkt igjen å bli med, så vi kan velge mellom CE og BE. Minimumsvekten som kan koble treet vårt til det er 1, og Prims algoritme velger det:

Ettersom alle knutepunktene i inngangsgrafen nå er tilstede i utdata-treet, slutter Prims algoritme. Derfor er dette treet en MST for inngangsgrafen.

4. Gjennomføring

Vertices og kanter lager grafer, så vi trenger en datastruktur for å lagre disse elementene. La oss lage klassen Kant:

offentlig klasse Edge {privat int vekt; privat boolsk isIncluded = false; }

Hver Kant må ha en vekt siden Prims algoritme fungerer på vektede grafer. er inkludert viser om Kant er tilstede i det minste spennende treet eller ikke.

La oss nå legge til Vertex klasse:

offentlig klasse Vertex {private String label = null; private Map edge = new HashMap (); privat boolsk isVisited = false; }

Hver Vertex kan valgfritt ha en merkelapp. Vi bruker kanter kart for å lagre forbindelser mellom hjørner. Endelig, isVisited viser om toppunktet har blitt besøkt av Prims algoritme så langt eller ikke.

La oss lage våre Prim klasse der vi implementerer logikken:

offentlig klasse Prim {privat liste graf; }

En liste over hjørner er nok til å lagre hele grafen fordi inne i hver Vertex, vi har en Kart for å identifisere alle forbindelser. Innsiden Prim, vi lager en løpe() metode:

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

Vi starter med å sette det første elementet i Listegraf som besøkt. Det første elementet kan være hvilken som helst av toppunktene, avhengig av rekkefølgen de er lagt til i utgangspunktet. isDisconnected () returnerer ekte hvis det er noen Vertex ikke besøkt så langt:

private boolean isDisconnected () {for (Vertex toppunkt: graf) {if (! vertex.isVisited ()) {return true; }} returner falsk; }

Mens minimum spenner treet isDisconnected (), sløyfer vi over de allerede besøkte hjørnene og finner Kant med minimumsvekt som kandidat til nesteVertex:

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 nytt par (nextVertex, nextMinimum); }

Vi finner minimum av alle kandidats i hovedsløyfen og lagre den i nesteVertex. Så satte vi oss nesteVertex som besøkt. Sløyfen fortsetter til alle hjørnene blir besøkt.

På slutten, Hver Kant med er inkludert lik ekte er tilstede.

Merk at siden nesteMinimum () det går gjennom kantene, er tidskompleksiteten til denne implementeringen O (V2). Hvis vi lagrer kantene i en prioritetskø (sortert etter vekt) i stedet, vil algoritmen utføre i O (E log V).

5. Testing

Ok, så nå som vi har fått litt kode, la oss teste den med et reelt eksempel. Først konstruerer vi grafen vår:

public static List createGraph () {List graph = new 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 = new Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... graph.add (e); retur graf; }

Konstruktøren av Prim klassen tar den og lagrer den inne i klassen. Vi kan skrive ut inngangsgrafen med originalGraphToString () metode:

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

Eksemplet vårt vil gi ut:

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

Nå kjører vi Prims algoritme og skriver ut den resulterende MST med minimumSpanningTreeToString () metode:

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

Til slutt skriver vi ut vår MST:

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

6. Konklusjon

I denne artikkelen lærte vi hvordan Prims algoritme finner et minimum av tre i en graf. Koden er tilgjengelig på GitHub.