streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban először megtudhatjuk, hogy mi a legkisebb átívelő fa. Ezután a Prim algoritmusát használjuk annak megtalálásához.

2. Minimális átfogó fa

A minimális átfogó fa (MST) egy súlyozott, irányítatlan, összekapcsolt gráf, amelynek teljes éltömegét a nehezebb élek eltávolításával minimalizálták. Más szavakkal, a gráf összes csúcsát érintetlenül tartjuk, de eltávolíthatunk néhány élet, így az összes él összege minimális lesz.

Súlyozott gráffal kezdjük, mivel nincs értelme a teljes éltömeg minimalizálására, ha ezeknek az éleknek egyáltalán nincs súlya. Vessen egy pillantást egy grafikonra:

A fenti grafikon egy súlyozott, irányítatlan, összekapcsolt grafikon. Itt van a grafikon MST-je:

A grafikon MST-je azonban nem egyedi. Ha egy grafikonnak egynél több MST-je van, akkor mindegyik MST-nek ugyanaz az összes éltömege.

3. Prim algoritmusa

Prim algoritmusa egy súlyozott, irányítatlan, összekapcsolt gráfot vesz bemenetként, és ennek a gráfnak az MST-jét adja eredményül.

Kapzsi módon működik. Az első lépésben kiválaszt egy tetszőleges csúcsot. Ezután, minden új lépés hozzáadja a legközelebbi csúcsot az eddig felépített fához amíg nem marad leválasztott csúcs.

Futtassuk a Prim algoritmust ezen a grafikonon lépésről lépésre:

Feltételezve, hogy az algoritmus elindításához tetszőleges csúcs B, három választási lehetőségünk van: A, C és E. Az élek megfelelő súlya 2, 2 és 5, ezért a minimum 2. Ebben az esetben két élünk van, amelyek súlya 2, így bármelyiket választhatjuk (mindegy, melyik). Válasszunk A-t:

Most van egy fa, amelynek két A és B csúcsa van. Kiválaszthatjuk a még hozzá nem adott A vagy B élek bármelyikét, amely egy hozzá nem csatolt csúcshoz vezet. Tehát választhatunk AC-t, BC-t vagy BE-t.

Prim algoritmusa a minimumot választja, amely 2 vagy BC:

Most van egy fa, amelynek három csúcsa és három lehetséges éle van az előrelépéshez: CD, CE vagy BE. Az AC nincs benne, mivel nem adna hozzá új csúcsot a fához. A minimális súly e három között 1.

Van azonban két él, amelyek mindegyike súlya 1. Következésképpen Prim algoritmusa közülük az egyiket választja (megint nem mindegy, melyiket) ebben a lépésben:

Csak egy csúcs maradt a csatlakozáshoz, így választhatunk CE és BE közül. A fánkat összekapcsoló minimális súly 1, és Prim algoritmusa választja ki:

Mivel a bemeneti gráf minden csúcsa jelen van a kimeneti fában, Prim algoritmusa véget ér. Ezért ez a fa a bemeneti grafikon MST-je.

4. Végrehajtás

A csúcsok és élek grafikonokat készítenek, ezért ezen elemek tárolásához adatstruktúrára van szükségünk. Hozzuk létre az osztályt Él:

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

Minden egyes Él kell a súly mivel Prim algoritmusa súlyozott grafikonokon működik. isIncluded megmutatja, hogy a Él van-e a minimális átívelő fában, vagy sem.

Most tegyük hozzá a Csúcs osztály:

public class Vertex {private String label = null; privát térképélek = new HashMap (); privát logikai isVisited = hamis; }

Minden egyes Csúcs opcionálisan lehet egy címke. Használjuk a élek térkép a kapcsolatok tárolásához a csúcsok között. Végül, isVisited megmutatja, hogy a csúcsot Prim algoritmusa látogatta-e eddig vagy sem.

Hozzuk létre a sajátunkat Pedáns osztály, ahol megvalósítjuk a logikát:

public class Prim {privát lista grafikon; }

A csúcsok listája elegendő az egész gráf tárolásához, mert mindegyiken belül Csúcs, nekünk van Térkép az összes kapcsolat azonosítására. Belül Pedáns, létrehozunk egy fuss() módszer:

public void run () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } while (isDisconnected ()) {Edge nextMinimum = új Edge (Integer.MAX_VALUE); Vertex nextVertex = graph.get (0); for (Vertex vertex: graph) {if (vertex.isVisited ()) {Párosjelölt = vertex.nextMinimum (); if (jelölt.getValue (). getWeight () <következőMinimum.getWeight ()) {nextMinimum = jelölt.getValue (); következőVertex = jelölt.getKey (); }}} nextMinimum.setIncluded (true); nextVertex.setVisited (true); }}

Kezdjük azzal, hogy beállítjuk a Lista grafikon ahogy meglátogatták. Az első elem bármelyik csúcs lehet, attól függően, hogy milyen sorrendben vették fel őket a listára. isDisconnected () visszatér igaz ha van ilyen Csúcs eddig nem látogatott:

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

Míg a minimális átívelő fa isDisconnected (), a már meglátogatott csúcsok fölé hurkolunk és megtaláljuk a Él minimális súllyal jelöltként következőVertex:

public Pair nextMinimum () {Edge nextMinimum = new Edge (Integer.MAX_VALUE); Vertex nextVertex = ez; Iterátor it = élek.entrySet () .iterator (); while (it.hasNext ()) {Map.Entry pár = it.next (); if (! pair.getKey (). isVisited ()) {if (! pair.getValue (). isIncluded ()) {if (pair.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = pár .getValue (); nextVertex = pair.getKey (); }}}} return new Pair (nextVertex, nextMinimum); }

Megtaláljuk az összes minimumot jelölts a fő hurokban, és tárolja benne következőVertex. Aztán beállítottuk következőVertex ahogy meglátogatták. A hurok addig folytatódik, amíg az összes csúcsot meg nem látogatja.

A végén, minden egyes Él val vel isIncluded egyenlő igaz jelen van.

Vegye figyelembe, hogy mivel következőMinimum () a szélein keresztül ismétlődik, a megvalósítás időbeli összetettsége O (V2). Ha az éleket egy prioritási sorban (súly szerint rendezve) tároljuk, akkor az algoritmus be fog teljesíteni O (E log V).

5. Tesztelés

Oké, szóval most, hogy van egy kis kódunk, teszteljük egy valós példával. Először elkészítjük a grafikonunkat:

public static List createGraph () {List graph = new ArrayList (); Csúcs a = új csúcs ("A"); ... csúcs e = új csúcs ("E"); Ab szél = új él (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = új Edge (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (a); ... gráf.add (e); visszatérő grafikon; }

A kivitelező Pedáns osztály elveszi és az osztályon belül tárolja. A bemeneti gráfot kinyomtathatjuk originalGraphToString () módszer:

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

Példánk a következőket adja ki:

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

Most lefuttatjuk a Prim algoritmust, és a kapott MST-t kinyomtatjuk minimumSpanningTreeToString () módszer:

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

Végül kinyomtatjuk az MST-t:

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

6. Következtetés

Ebben a cikkben megtudtuk, hogyan találja meg Prim algoritmusa a gráf minimális átfogó fáját. A kód elérhető a GitHubon.