DFS
Lekcja 11 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Przeszukiwanie w głąb najpierw zagłębia się, a dopiero potem wszerz. Zaczynając od wierzchołka, podąża jedną krawędzią tak daleko, jak to możliwe, a następnie cofa się i próbuje kolejnej. Wersja iteracyjna używa stosu: zdejmuje wierzchołek ze stosu, zapisuje go, a nieodwiedzonych sąsiadów ponownie umieszcza na stosie.
Aby DFS zwracało deterministyczną kolejność przechodzenia w tym wyzwaniu, umieszczaj sąsiadów na stosie w kolejności malejącej. Dzięki temu najmniejszy sąsiad znajdzie się na szczycie stosu i zostanie przetworzony jako pierwszy, co odpowiada kolejności uzyskiwanej przez rekurencyjne DFS przechodzące po sąsiadach w kolejności rosnącej.
Uważaj, aby wierzchołek nie został umieszczony na stosie dwa razy (różni sąsiedzi mogą mieć wspólnego sąsiada). Na początku pętli sprawdzaj zbiór odwiedzonych wierzchołków i pomijaj wierzchołek, jeśli został już odwiedzony.
Wyzwanie
ŁatwyNapisz funkcję dfs, która przyjmuje dwuwymiarową tablicę int adjacency (każdy wiersz to krawędź [u, v]) i int start, a następnie zwraca kolejność odwiedzania w DFS od start w postaci listy intów.
Zbuduj graf, dodając każdą krawędź. Iteracyjny DFS z użyciem stosu: zdejmij wierzchołek ze stosu, jeśli nie został odwiedzony, zapisz go i dodaj jego sąsiadów w kolejności posortowanej malejąco, aby jako pierwszy został przetworzony najmniejszy.
Musisz użyć klasy Graph (dostępnej w graph) — nie używaj wbudowanych elementów języka (map, zbiorów) do modelowania list sąsiedztwa. Pomocnicze struktury danych na potrzeby algorytmu (zbiory odwiedzonych wierzchołków, stosy) mogą korzystać z typów biblioteki standardowej.
Spróbuj swoich sił
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}
Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9
Poćwicz samodzielnie: Kompilator C online