streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megismerkedünk a Breadth-First Search algoritmussal, amely lehetővé teszi számunkra, hogy csomópontot keressünk egy fában vagy egy grafikonon, úgy, hogy a csomópontjaikat szélességben, nem pedig a mélység előtt haladjuk át.

Először áttekintünk egy kis elméletet erről a fák és grafikonok algoritmusáról. Ezt követően elmélyülünk a Java algoritmusok megvalósításában. Végül kitérünk az idő összetettségére.

2. Szélesség-első keresési algoritmus

A Breadth-First Search (BFS) algoritmus alapvető megközelítése az, hogy csomópontot keressen egy fába vagy grafikonszerkezetbe a gyermekek előtti szomszédok feltárásával.

Először meglátjuk, hogyan működik ez az algoritmus a fák esetében. Ezt követően a grafikonokhoz igazítjuk, amelyeknek sajátos korlátja van, hogy néha ciklusokat tartalmazzanak. Végül megvitatjuk ennek az algoritmusnak a teljesítményét.

2.1. Fák

A fákra vonatkozó BFS algoritmus ötlete az, hogy fenntartani a csomópontok sorát, amely biztosítja az áthaladás rendjét. Az algoritmus elején a sor csak a gyökércsomópontot tartalmazza. Megismételjük ezeket a lépéseket, amíg a sor még tartalmaz egy vagy több csomópontot:

• Tegye be az első csomópontot a sorból
• Ha ez a csomópont az, amelyet keresünk, akkor a keresésnek vége
• Ellenkező esetben vegye fel a csomópont gyermekeit a sor végére, és ismételje meg a lépéseket

A végrehajtás befejezését a ciklusok hiánya biztosítja. A ciklusok kezeléséről a következő szakaszban olvashatunk.

2.2. Grafikonok

Grafikonok esetén a struktúrában lehetséges ciklusokra kell gondolnunk. Ha egyszerűen alkalmazzuk az előző algoritmust egy grafikonon egy ciklussal, akkor az örökké ciklusos lesz. Ebből kifolyólag, meg kell őriznünk a meglátogatott csomópontok gyűjteményét, és gondoskodnunk arról, hogy ne keressük fel őket kétszer:

• Tegye be az első csomópontot a sorból
• Ellenőrizze, hogy a csomópont már meglátogatott-e, ha igen, hagyja ki
• Ha ez a csomópont az, amelyet keresünk, akkor a keresésnek vége
• Ellenkező esetben adja hozzá a meglátogatott csomópontokhoz
• Adja hozzá ennek a csomópontnak a gyermekeit a sorba, és ismételje meg ezeket a lépéseket

3. Megvalósítás Java-ban

Most, hogy az elméletet áttekintettük, vegyük kezünkbe a kódot, és valósítsuk meg ezeket az algoritmusokat Java-ban!

3.1. Fák

Először implementáljuk a fa algoritmust. Tervezzük meg Fa osztály, amely egy értékből és a gyerekek listájából áll Fas:

public class Tree {private T value; privát lista gyermekek; privát fa (T érték) {this.value = érték; this.children = new ArrayList (); } public static Tree of (T érték) {return new tree (value); } public tree addChild (T érték) {Tree newChild = új fa (érték); gyerekek.add (newChild); return newChild; }}

A ciklusok létrehozásának elkerülése érdekében a gyerekeket maga az osztály hozza létre, egy adott érték alapján.

Ezt követően adjuk meg a keresés() módszer:

nyilvános statikus Opcionális keresés (T érték, fa gyökér) {// ...}

Mint korábban említettük, a BFS algoritmus egy várólistát használ a csomópontok áthaladásához. Először is hozzáadjuk a sajátunkat gyökér csomópont ehhez a sorhoz:

Sor sor = new ArrayDeque (); queue.add (root);

Ezután folytatnunk kell a ciklust, amíg a sor nem üres, és minden egyes alkalommal kiugrunk egy csomópontot a sorból:

while (! queue.isEmpty ()) {Tree currentNode = queue.remove (); }

Ha ez a csomópont az, amelyet keresünk, visszaküldjük, különben felvesszük gyermekeit a sorba:

if (currentNode.getValue (). egyenlő (érték)) {return Opcionális.of (currentNode); } else {queue.addAll (currentNode.getChildren ()); }

Végül, ha az összes csomópontot meglátogattuk anélkül, hogy megtaláltuk volna a keresettet, akkor üres eredményt adunk vissza:

return Opcionális.empty ();

Most képzeljünk el egy példa a fa szerkezetére:

Ami Java kódot jelent:

Fa gyökere = Tree.of (10); Fa gyökérFirstChild = root.addChild (2); Fa mélységeMostChild = rootFirstChild.addChild (3); Fa gyökérSecondChild = gyökér.addChild (4);

Ezután, ha a 4. értéket keressük, akkor azt várjuk, hogy az algoritmus a 10., 2. és 4. értékű csomópontokat a következő sorrendben haladja meg:

BreadthFirstSearchAlgorithm.search (4, root)

Ellenőrizhetjük, hogy a meglátogatott csomópontok értékének naplózásával:

[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Meglátogatott csomópont értéke: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Meglátogatott csomópont értéke: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Meglátogatott csomópont

3.2. Grafikonok

Ezzel lezárul a fák esete. Most nézzük meg, hogyan kell kezelni a grafikonokat. A fákkal ellentétben a grafikonok ciklusokat tartalmazhatnak. Ez azt jelenti, amint azt az előző szakaszban láthattuk, emlékeznünk kell a meglátogatott csomópontokra, hogy elkerüljük a végtelen hurkot. Egy pillanat múlva meglátjuk, hogyan kell frissíteni az algoritmust, figyelembe véve ezt a problémát, de először definiáljuk a gráf struktúránkat:

public class Csomópont {private T value; privát készlet szomszédok; public Node (T érték) {this.value = érték; this. szomszédok = new HashSet (); } public void connect (Csomópont csomópont) {if (ez == csomópont) új IllegalArgumentException-t dob ​​("Nem lehet csomópontot összekapcsolni önmagával"); ez.szomszédok.add (csomópont); csomópont.szomszédok.add (ezt); }}

Most láthatjuk, hogy a fákkal szemben szabadon összekapcsolhatunk egy csomópontot egy másikkal, lehetőséget adva ciklusok létrehozására. Az egyetlen kivétel az, hogy egy csomópont nem tud csatlakozni önmagához.

Azt is érdemes megjegyezni, hogy ezzel az ábrázolással nincs gyökércsomópont. Ez nem jelent problémát, mivel a csomópontok közötti kapcsolatokat kétirányúvá is tettük. Ez azt jelenti, hogy bármely csomóponttól kezdve kereshetünk a grafikonon.

Először is használjuk újra az algoritmust felülről, az új struktúrához igazítva:

nyilvános statikus Opcionális keresés (T érték, csomópont kezdete) {várólista sor = new ArrayDeque (); queue.add (start); Node currentNode; while (! queue.isEmpty ()) {currentNode = queue.remove (); if (currentNode.getValue (). egyenlő (érték)) {return Opcionális.of (currentNode); } else {queue.addAll (currentNode.getNeighbors ()); }} return Opcionális.empty (); }

Nem tudjuk így futtatni az algoritmust, vagy bármely ciklus örökre futni fogja. Tehát utasításokat kell hozzáadnunk a már meglátogatott csomópontok gondozásához:

while (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Meglátogatott csomópont értékével: {}", currentNode.getValue ()); if (currentNode.getValue (). egyenlő (érték)) {return Opcionális.of (currentNode); } else {alreadyVisited.add (currentNode); queue.addAll (currentNode.getNeighbors ()); queue.removeAll (már meglátogatott); }} return Opcionális.empty ();

Mint láthatjuk, először inicializáljuk a Készlet amely tartalmazza a meglátogatott csomópontokat.

Készlet alreadyVisited = új HashSet ();

Azután, ha az értékek összehasonlítása sikertelen, hozzáadjuk a csomópontot a meglátogatottakhoz:

márVisited.add (currentNode);

Végül, miután a csomópont szomszédait felvette a sorba, eltávolítjuk belőle a már meglátogatott csomópontokat (amely egy alternatív módszer az aktuális csomópont jelenlétének ellenőrzésére az adott halmazban):

queue.removeAll (már meglátogatott);

Ezzel biztosítjuk, hogy az algoritmus ne essen végtelen ciklusba.

Nézzük meg, hogyan működik ez egy példán keresztül. Először meghatározunk egy grafikont egy ciklussal:

És ugyanez a Java kódban:

Csomópont kezdete = új Csomópont (10); Node firstNeighbor = új Node (2); start.connect (firstNeighbor); Node firstNeighborNeighbor = új Csomópont (3); firstNeighbor.connect (firstNeighborNeighbor); firstNeighborNeighbor.connect (start); Node secondNeighbor = új Csomópont (4); start.connect (secondNeighbor);

Ismételjük meg, hogy meg akarjuk keresni a 4. értéket. Mivel nincs gyökércsomópont, a keresést bármelyik kívánt csomópontmal megkezdhetjük, és kiválasztjuk firstSzomszédSzomszéd:

BreadthFirstSearchAlgorithm.search (4, firstNeighborNeighbor);

Ismét hozzáadunk egy naplót annak megtekintéséhez, hogy mely csomópontok látogattak meg, és arra számítunk, hogy 3, 2, 10 és 4 lesznek, csak egyszer, sorrendben:

[main] INFO cbabBreadthFirstSearchAlgorithm - Meglátogatott csomópont értékkel: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Meglátogatott csomópont értékkel: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - Meglátogatott csomópont értékkel: 10 [main] : 4

3.3. Bonyolultság

Most, hogy mindkét algoritmust lefedtük a Java-ban, beszéljünk azok időbeli összetettségéről. Kifejezésükre a Big-O jelölést használjuk.

Kezdjük a fa algoritmussal. Legfeljebb egyszer ad egy csomópontot a sorhoz, ezért legfeljebb egyszer meglátogatja azt is. Így ha n a csomópontok száma a fában, az algoritmus időbeli összetettsége lesz Tovább).

Most, a gráf algoritmus esetében a dolgok egy kicsit bonyolultabbak. Minden csomópontot legfeljebb egyszer fogunk végigmenni, de ehhez lineáris komplexitású műveleteket fogunk használni, mint pl az összes hozzáadása() és összes eltávolítása().

Vegyük fontolóra n a csomópontok száma és c a grafikon kapcsolatai száma. Ezután a legrosszabb esetben (mivel nem található csomópont) használhatjuk az összes hozzáadása() és összes eltávolítása() metódusok a csomópontok hozzáadásához és eltávolításához a kapcsolatok számáig, megadva nekünk O (c) ezeknek a műveleteknek a bonyolultsága. Tehát, feltéve, hogy c> n, a teljes algoritmus bonyolultsága az lesz O (c). Különben az lesz Tovább). Ezt általában megjegyzik O (n + c), amely komplexitásként értelmezhető a közöttük lévő legnagyobb szám függvényében n és c.

Miért nem volt ilyen problémánk a fakeresésnél? Mivel egy fában a kapcsolatok számát a csomópontok száma határolja. A kapcsolatok száma a n csomópontok az n - 1.

4. Következtetés

Ebben a cikkben megismerkedtünk a Breadth-First Search algoritmussal és annak Java alkalmazásával.

Miután elmélkedtünk egy kis elmélettel, láttuk az algoritmus Java implementációit és megbeszéltük annak komplexitását.

Szokás szerint a kód elérhető a GitHubon.