streamalism.org

1. Prehľad

V tomto výučbe sa dozvieme o algoritme vyhľadávania na šírku, ktorý nám umožňuje vyhľadať uzol na strome alebo v grafe tak, že prejdeme ich uzlami skôr po šírke ako po hĺbke.

Najprv si prejdeme trochu teórie o tomto algoritme pre stromy a grafy. Potom sa ponoríme do implementácií algoritmov v Jave. Na záver sa budeme venovať ich časovej zložitosti.

2. Algoritmus vyhľadávania na šírku

Základným prístupom algoritmu BFS k hľadaniu na prvom mieste je vyhľadanie uzla v stromovej alebo grafickej štruktúre skúmaním susedov pred deťmi.

Najprv uvidíme, ako tento algoritmus funguje pre stromy. Potom to prispôsobíme grafom, ktoré majú špecifické obmedzenia, ktoré niekedy obsahujú cykly. Na záver si povieme niečo o výkonnosti tohto algoritmu.

2.1. Stromy

Myšlienka algoritmu BFS pre stromy je: udržiavať frontu uzlov, ktorá zabezpečí poradie prechodu. Na začiatku algoritmu obsahuje rad iba koreňový uzol. Tieto kroky budeme opakovať, pokiaľ fronta stále obsahuje jeden alebo viac uzlov:

• Vyberte prvý uzol z frontu
• Ak tento uzol hľadáme, hľadanie skončilo
• V opačnom prípade pridajte deti tohto uzla na koniec poradia a kroky opakujte

Ukončenie výkonu je zabezpečené absenciou cyklov. Uvidíme, ako zvládnuť cykly v ďalšej časti.

2.2. Grafy

V prípade grafov musíme myslieť na možné cykly v štruktúre. Ak jednoducho použijeme predchádzajúci algoritmus na graf s cyklom, bude sa cyklovať navždy. Preto budeme musieť uchovať zbierku navštívených uzlov a zabezpečiť, aby sme ich nenavštívili dvakrát:

• Vyberte prvý uzol z frontu
• Skontrolujte, či uzol už bol navštívený, ak áno, preskočte ho
• Ak tento uzol hľadáme, hľadanie skončilo
• V opačnom prípade ho pridajte do navštívených uzlov
• Pridajte deti tohto uzla do poradia a zopakujte tieto kroky

3. Implementácia v Jave

Teraz, keď je táto teória obsiahnutá, poďme spolu do kódu a implementujme tieto algoritmy v Jave!

3.1. Stromy

Najskôr implementujeme stromový algoritmus. Poďme navrhnúť naše Strom triedy, ktorá sa skladá z hodnoty a detí predstavovaných zoznamom ďalších Stroms:

verejná trieda Strom {súkromná hodnota T; súkromný zoznam deti; súkromný strom (hodnota T) {this.value = hodnota; this.children = new ArrayList (); } public static Tree of (T value) {return new Tree (value); } verejný strom addChild (hodnota T) {Tree newChild = nový strom (hodnota); deti.pridat (newChild); návrat newChild; }}

Aby sa zabránilo vytváraniu cyklov, deti vytvára trieda sama na základe danej hodnoty.

Potom poskytneme a Vyhľadávanie() metóda:

public static Voliteľné hľadať (hodnota T, koreň stromu) {// ...}

Ako sme už spomínali, algoritmus BFS používa na prechádzanie uzlami frontu. Najskôr pridáme naše koreň uzol do tohto poradia:

Fronta front = new ArrayDeque (); queue.add (root);

Potom musíme urobiť slučku, kým fronta nie je prázdna, a zakaždým, keď vysunieme uzol z fronty:

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

Ak ten uzol hľadáme, vrátime ho, inak pridáme jeho deti do poradia:

if (currentNode.getValue (). equals (value)) {return Optional.of (currentNode); } else {queue.addAll (currentNode.getChildren ()); }

Nakoniec, ak sme navštívili všetky uzly bez toho, aby sme našli ten, ktorý hľadáme, vrátime prázdny výsledok:

vrátiť Optional.empty ();

Poďme si teraz predstaviť príklad stromovej štruktúry:

Čo sa prekladá do kódu Java:

Koreň stromu = Tree.of (10); Root stromuFirstChild = root.addChild (2); Depth of treeMostChild = rootFirstChild.addChild (3); Root stromuSecondChild = root.addChild (4);

Ak potom hľadáme hodnotu 4, očakávame, že algoritmus bude prechádzať uzlami s hodnotami 10, 2 a 4 v tomto poradí:

BreadthFirstSearchAlgorithm.search (4, root)

Môžeme to overiť protokolovaním hodnoty navštívených uzlov:

[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 4

3.2. Grafy

Tým sa prípad stromov končí. Poďme sa teraz pozrieť, ako naložiť s grafmi. Na rozdiel od stromov môžu grafy obsahovať cykly. To znamená, ako sme videli v predchádzajúcej časti, musíme si pamätať uzly, ktoré sme navštívili, aby sme sa vyhli nekonečnej slučke. O chvíľu uvidíme, ako aktualizovať algoritmus tak, aby zohľadňoval tento problém, ale najskôr si zadefinujme našu štruktúru grafu:

verejná trieda Uzol {súkromná hodnota T; súkromná sada susedia; public Node (hodnota T) {this.value = hodnota; this.ne Neighbors = new HashSet (); } public void connect (uzol uzla) {if (this == node) throw new IllegalArgumentException ("Cannot connect node to itself"); this.ne Neighbors.add (uzol); node.ne Neighbors.add (toto); }}

Teraz vidíme, že na rozdiel od stromov môžeme ľubovoľne spojiť uzol s iným, čo nám dáva možnosť vytvárať cykly. Jedinou výnimkou je, že sa uzol nemôže pripojiť sám k sebe.

Je tiež potrebné poznamenať, že s týmto znázornením neexistuje žiadny koreňový uzol. To nie je problém, pretože sme tiež vytvorili obojsmerné spojenia medzi uzlami. To znamená, že budeme môcť prehľadávať graf od ktoréhokoľvek uzla.

Najskôr použijeme zhora algoritmus prispôsobený novej štruktúre:

public static Voliteľné vyhľadávanie (hodnota T, začiatok uzla) {front front = new ArrayDeque (); queue.add (štart); Uzol currentNode; while (! queue.isEmpty ()) {currentNode = queue.remove (); if (currentNode.getValue (). equals (value)) {return Optional.of (currentNode); } else {queue.addAll (currentNode.getNe Neighbors ()); }} vrátiť Optional.empty (); }

Algoritmus nemôžeme spustiť takto, inak ho ľubovoľný cyklus nechá bežať navždy. Musíme teda pridať pokyny, aby sme sa postarali o už navštívené uzly:

while (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Navštívený uzol s hodnotou: {}", currentNode.getValue ()); if (currentNode.getValue (). equals (value)) {return Optional.of (currentNode); } else {alreadyVisited.add (currentNode); queue.addAll (currentNode.getNe Neighbors ()); queue.removeAll (alreadyVisited); }} vrátiť Optional.empty ();

Ako vidíme, najskôr inicializujeme a Nastaviť ktoré budú obsahovať navštívené uzly.

Nastaviť alreadyVisited = nový HashSet ();

Potom, keď zlyhá porovnanie hodnôt, pridáme uzol k navštíveným:

alreadyVisited.add (currentNode);

Nakoniec po pridaní susedov uzla do fronty z neho odstránime už navštívené uzly (čo je alternatívny spôsob kontroly prítomnosti aktuálneho uzla v tejto sade):

queue.removeAll (alreadyVisited);

Týmto zaistíme, že algoritmus nespadne do nekonečnej slučky.

Pozrime sa, ako to funguje, na príklade. Najskôr definujeme graf s cyklom:

A to isté v kóde Java:

Začiatok uzla = nový uzol (10); Uzol prvýSused = nový Uzol (2); start.connect (firstNe Neighbor); Uzol firstNe NeighborNe Neighbor = nový Uzol (3); firstNe Neighbor.connect (firstNe NeighborNe Neighbor); firstNe NeighborNe Neighbor.connect (štart); Uzol druhýSused = nový Uzol (4); start.connect (secondNe Neighbor);

Znova povedzme, že chceme vyhľadať hodnotu 4. Pretože neexistuje žiadny koreňový uzol, môžeme začať hľadať s akýmkoľvek uzlom, ktorý chceme, a vyberieme firstSusedSused:

BreadthFirstSearchAlgorithm.search (4, firstNe NeighborNe Neighbor);

Opäť pridáme protokol, aby sme zistili, ktoré uzly sú navštívené, a očakávame, že budú 3, 2, 10 a 4, iba raz v tomto poradí:

[main] INFO cbabBreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - Navštívený uzol s hodnotou: 10 [hlavný] INFO cbabBreadthFirstSearchAlgor : 4

3.3. Zložitosť

Teraz, keď sme sa oba algoritmy venovali v Jave, poďme si povedať o ich časovej zložitosti. Na ich vyjadrenie použijeme notáciu Big-O.

Začnime stromovým algoritmom. Pridá uzol do fronty najviac raz, preto ho navštívi tiež najviac raz. Teda ak n je počet uzlov v strome, bude časová zložitosť algoritmu O (n).

Teraz je to s algoritmom grafu trochu komplikovanejšie. Každý uzol prejdeme nanajvýš raz, ale využijeme na to operácie, ktoré majú lineárnu zložitosť ako napr pridať všetko() a odobrať všetky().

Uvažujme n počet uzlov a c počet pripojení grafu. V najhoršom prípade (ak sa nenájde žiadny uzol) môžeme použiť pridať všetko() a odobrať všetky() metódy pridávania a odstraňovania uzlov až do počtu pripojení, čo nám dáva O (c) zložitosť týchto operácií. Takže za predpokladu, že c> n, bude zložitosť celkového algoritmu O (c). Inak to bude O (n). Toto sa všeobecne zaznamenáva O (n + c), ktoré možno interpretovať ako zložitosť v závislosti od najväčšieho počtu medzi n a c.

Prečo sme nemali tento problém s hľadaním stromu? Pretože počet spojení v strome je ohraničený počtom uzlov. Počet pripojení v strome n uzlov je n - 1.

4. Záver

V tomto článku sme sa dozvedeli o algoritme Breadth-First Search a o tom, ako ho implementovať v prostredí Java.

Po absolvovaní trochu teórie sme videli implementácie algoritmu v jazyku Java a diskutovali o jeho zložitosti.

Ako obvykle je kód k dispozícii na GitHub.