Algorytm przeszukiwania w głab (DFS)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
antolek
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 12 paź 2017, o 11:14
Płeć: Mężczyzna
Lokalizacja: Poznań

Algorytm przeszukiwania w głab (DFS)

Post autor: antolek » 16 paź 2017, o 15:21

Zad. Do grafu podanym na rysunku zastosować algorytm przeszukiwania w głab (DFS). Zaczynając od wierzchołka a i rozpatrując wierzchołki w kolejności alfabetycznej. Zanotuj dla DFS stany stosu i krawędzie kolejno dodawane do drzewa.

Prosiłbym o sprawdzenie mojego rozwiazania. (Mogę podać w razie potrzeby sposób na jakim sie wzorowałem)

\(\displaystyle{ \begin{tabular}{|c|c|c|} \hline Odwiedzone & Stos & Krawędzie \\ \hline a & i, h, g, e, b & - \\ \hline b & f, e, c & ab \\ \hline c & h, f, e, d & bc \\ \hline d & - & dc \\ \hline e & h & ce \\ \hline h & i & eh \\ \hline i & - & hi \\ \hline f & - & cf \\ \hline g & - & ag \\ \hline \end{tabular}}\)


Mruczek
Użytkownik
Użytkownik
Posty: 1111
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 155 razy

Re: Algorytm przeszukiwania w głab (DFS)

Post autor: Mruczek » 20 lis 2017, o 19:33

Jest źle.
W pierwszym kroku wrzuciłeś na stos i, h, g, e, b, potem ściągnąłeś z niego b i zgubiłeś pozostałe elementy znajdujące się na stosie. W drugim wierszu stos powinien wyglądać tak: i, h, g, e, f, e, c.

ODPOWIEDZ