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ę.
Rysowanie drzewa przeglądu grafu wgłąb i wszerz
-
- Użytkownik
- Posty: 266
- Rejestracja: 11 cze 2018, o 19:12
- Płeć: Kobieta
- Lokalizacja: Płock
- Podziękował: 69 razy
- Dasio11
- Moderator
- Posty: 10218
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Rysowanie drzewa przeglądu grafu wgłąb i wszerz
https://pl.wikipedia.org/wiki/Przeszukiwanie_w_głąb
https://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz
-
- Użytkownik
- Posty: 266
- Rejestracja: 11 cze 2018, o 19:12
- Płeć: Kobieta
- Lokalizacja: Płock
- Podziękował: 69 razy
Re: Rysowanie drzewa przeglądu grafu wgłąb i wszerz
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ę.
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
- Moderator
- Posty: 10218
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Rysowanie drzewa przeglądu grafu wgłąb i wszerz
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).
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).
-
- Użytkownik
- Posty: 266
- Rejestracja: 11 cze 2018, o 19:12
- Płeć: Kobieta
- Lokalizacja: Płock
- Podziękował: 69 razy
Re: Rysowanie drzewa przeglądu grafu wgłąb i wszerz
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:
-przykład w głąb:
-przykład wszerz: