Przeszukiwanie wszerz

Z Wikipedii

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf podgraf cykl klika stopień wierzchołka dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Przeszukiwanie wszerz
Kolejność odwiedzania węzłów
Podstawowe informacje
Klasa algorytmu: przeszukiwania Struktura danych: graf, drzewo Złożoność czasowa: O( | V | + | E | ) Złożoność pamięciowa: O( | V | + | E | ) Optymalny: nie Kompletny: tak

Przeszukiwanie wszerz (ang. Breadth-first search, w skrócie BFS) – w informatyce algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu.

Spis treści 1 Algorytm 2 Właściwości 2.1 Złożoność pamięciowa 2.2 Złożoność czasowa 2.3 Kompletność 3 Zastosowania przeszukiwania wszerz

[edytuj] Algorytm

funkcja przeszukiwanie_wszerz (Start, Cel) { 
    dodaj_do_kolejki(Kolejka, Start)
    dopóki nie_pusta(Kolejka) {
        Wierzchołek:= pobierz_z_kolejki(Kolejka)
        jeżeli Wierzchołek = Cel {
            zwróć Wierzchołek /*kod poniżej nie wykonuje się*/
        }
        dla każdego Syna w Wierzchołek {
            jeżeli nie_odwiedzony(Syn) {
                zapamiętaj_że_odwiedzony(Syn)
                dodaj_do_kolejki(Kolejka, Syn)
            }
        }
    }
}

[edytuj] Właściwości

[edytuj] Złożoność pamięciowa

Ponieważ trzeba utrzymywać listę węzłów które się już odwiedziło, złożoność pamięciowa przeszukiwania wszerz wynosi O(|V| + |E|), gdzie |V| to liczba węzłów, a |E| to liczba krawędzi w grafie. Z powodu tak dużego zapotrzebowania na pamięć przeszukiwanie wszerz jest niepraktyczne dla dużych danych.

[edytuj] Złożoność czasowa

Ponieważ w najgorszym przypadku przeszukiwanie wszerz musi przebyć wszystkie krawędzie prowadzące do wszystkich węzłów, złożoność czasowa przeszukiwania wszerz wynosi O(|V| + |E|), gdzie |V| to liczba węzłów, a |E| to liczba krawędzi w grafie.

[edytuj] Kompletność

Przeszukiwanie wszerz jest kompletne, to znaczy że gdy istnieje rozwiązanie, przeszukiwanie wszerz odnajdzie je niezależnie od grafu.

[edytuj] Zastosowania przeszukiwania wszerz

Przeszukiwanie wszerz może zostać użyte do rozwiązania wielu problemów z teorii grafów, dla przykładu:

• Odnalezienie wszystkich połączonych węzłów w grafie.
• Odnalezienie najkrótszej ścieżki między dwoma wierzchołkami (nie uwzględnia wag krawędzi w grafie ważonym).