Rysowanie drzewa przeglądu grafu wgłąb i wszerz

[Karolinaa0]

Narysuj drzewo przeglądu poniższego grafu wgłąb i wszerz zaczynając od wierzchołka 9.


Mam pytanie gdzie znajdę podobny przykład dokładnie omówiony, na którego podstawie będę mogła nauczyć się rysowania drzew przeglądu grafów wgłąb i wszerz albo mam pytanie jak kolokwialnie wyjaśnić na czym to polega? Z góry bardzo dziękuję.

[Dasio11]

https://pl.wikipedia.org/wiki/Przeszukiwanie_w_głąb
https://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz

[Karolinaa0]

Też to znalazłam, ale niestety nie wiem czy potrafię to zastosować w praktyce, tak zrobiłam ten przykład:

I mam pytanie czy udało mi się zrozumieć i zrobić je dobrze?
A jeśli chodzi o przeszukiwanie wgłąb, istnieje kilka możliwości rozwiązania, tak jak wstawiłam wyżej? W przeszukiwaniu w głąb chodzi o 1.)szukanie wierzchołka z najmniejszą liczbą wychodzących krawędzi i 2.) jeśli będzie kilka wierzchołków o takiej samej ilości krawędzi wychodzących, to wtedy wybieramy OBOJĘTNIE który czy ten z NAJMNIEJSZYM numerem czy może ten z NAJWIĘKSZYM numerem? Z góry bardzo dziękuję.

[Dasio11]

Wszystkie Twoje rozwiązania są dobre.

W obu algorytmach kolejność oglądania wierzchołków nie jest ściśle określona, stąd Twoje zadanie ma wiele poprawnych rozwiązań. Przetwarzanie pojedynczego wierzchołka \(\displaystyle{ v}\) polega zawsze na dołączeniu wszystkich dotychczas nieprzetworzonych sąsiadów \(\displaystyle{ v}\) do zbioru \(\displaystyle{ W}\) wierzchołków oczekujących na przetworzenie. Kolejność, w jakiej dołączamy tych sąsiadów do \(\displaystyle{ W}\), jest dowolna - na ogół nie bierze się pod uwagę ani liczby wychodzących krawędzi, ani numeru, ani niczego innego, lecz po prostu rozpatruje się je w takiej kolejności, w jakiej występują na liście sąsiadów \(\displaystyle{ v}\). Ważna jest natomiast kolejność, w jakiej wyciąga się wierzchołki z \(\displaystyle{ W}\) celem ich przetworzenia - przy przeszukiwaniu w głąb bierze się ten, który został dołączony do \(\displaystyle{ W}\) jako ostatni (FILO), a podczas przeszukiwania wszerz wyciąga się taki, który trafił do \(\displaystyle{ W}\) najwcześniej (FIFO).

[Karolinaa0]

Na wykładzie nie mieliśmy doprecyzowane czy trzeba patrzeć na najmniejszy numer wierzchołka czy jest on dowolny, dlatego chyba lepiej robić najmniejszym numerem wierzchołka, wtedy będzie bezpieczniej. I jedynie mam pytanie czy dobrze zrobiłam te dwa przykłady razem z algorytmami? Z góry bardzo dziękuję.
-przykład w głąb:

-przykład wszerz: