Implementacja (część 2)

Lekcja 6 z 9 w kursie Przeszukiwanie w głąb — algorytmy grafowe w Coddy.

Teraz przechodzimy cały graf za pomocą stosu.

Wyzwanie

Średni

Teraz zbuduj pełne przejście.

Napisz funkcję o nazwie dfs, która przyjmuje n, płaską tablicę edges (graf nieskierowany) oraz wierzchołek start, a następnie zwraca kolejność, w jakiej DFS odwiedza wierzchołki, zaczynając od start.

Najpierw zbuduj listę sąsiedztwa (posortuj sąsiadów każdego wierzchołka rosnąco). Następnie wykonaj iteracyjne DFS ze stosem. Odwiedzane są tylko wierzchołki osiągalne z start.

Aby odwiedzać sąsiadów w kolejności rosnącej, umieszczaj ich na stosie od największego do najmniejszego.

Spróbuj swoich sił

#include <stdlib.h>

int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = 0;
    return edges;
}