Rysowanie drzewa przeglądu grafu wgłąb i wszerz Karolina: Narysuj drzewo przeglądu poniższego grafu wgłąb i wszerz zaczynając od wierzchołka 9. https://pl-static.z-dn.net/files/d44/53c440dcd25854c1c905c890ab595f94.jpg 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ę

Karolina: Tak zrobiłam ten przykład: https://pl-static.z-dn.net/files/d01/f4f087bc6f65717ac836f584fa8e8ca5.jpg 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ę.

Pytający: I wszerz, i w głąb tak naprawdę nieistotna jest kolejność w jakiej rozpatrujemy sąsiadów danego wierzchołka. Różnica polega na tym, że w przeszukiwaniu wszerz najpierw rozpatrujemy po kolei wszystkich sąsiadów danego wierzchołka, a dopiero później sąsiadów tych sąsiadów itd., natomiast w przeszukiwaniu w głąb bierzemy pierwszego sąsiada danego wierzchołka, następnie rozpatrujemy jakiegoś sąsiada tego sąsiada itd. wchodzimy "w głąb" i dopiero powracając ("z głębi") przechodzimy do kolejnego sąsiada danego wierzchołka. Taka analogia: jakbyś miała wykopać w ziemi dół metr na metr na metr, to kopiąc wszerz byś zaznaczyła sobie ten kwadrat metr na metr i kopałabyś tak, żeby ten kwadrat cały czas był na równo, stopniowo obniżając go aż dół będzie miał metr głębokości. Kopiąc w głąb najpierw byś w owym kwadracie wykopała powiedzmy dół 10 cm na 10 cm na metr głębokości, następnie kolejny taki dół, itd. aż otrzymałabyś cały wymagany dół. Wszerz − najpierw jak najszerzej się da, później w głąb. W głąb − najpierw jak najgłębiej się da, później po szerokości. Co do drzew przez Ciebie narysowanych − wyglądają ok. Aczkolwiek przechodząc wszerz też można otrzymać inne drzewo (np. rozpatrując sąsiadów wierzchołka 9 w kolejności: 7, 6, 2). Co do warunków 1), 2) − nie są one bezpośrednio powiązane z algorytmami przechodzenia wszerz czy w głąb. Równie dobrze mógłbym CI powiedzieć "sąsiadów rozpatrujemy w kolejność od największego do najmniejszego indeksu". Nie wiem, czy dostałaś jakąś wytyczną co do kolejności przechodzenia sąsiadów.

Karolina: Dziękuję bardzo. 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 stosując dodatkowe założenie z najmniejszym numerem wierzchołka? Z góry bardzo dziękuję. −przykład w głąb: https://pl-static.z-dn.net/files/d43/a9 ... e32091.jpg −przykład wszerz: https://pl-static.z-dn.net/files/d6d/db ... 9e3cb4.jpg

Karolina: Wklejam jeszcze raz: − przykład w głąb: https://pl-static.z-dn.net/files/d43/a9547f90334303eb94ed8b7379e32091.jpg −przykład wszerz: https://pl-static.z-dn.net/files/d6d/db0642d650243d2ea0a340d6229e3cb4.jpg

Pytający: W głąb dobrze. Wszerz na końcu ciągu się machnęłaś (przecież sąsiadów dwójki rozpatrujesz według rosnących numerów wierzchołka). Powinno być: (9, 8, 10, 7, 11, 6, 2, 4, 1, 3, 5) Acz drzewo takie samo by wyszło.

Karolina: A tak, to zwykła pomyłka, dziękuję bardzo