Implementacja (część 2)

Lekcja 6 z 9 w kursie Przeszukiwanie wszerz — algorytmy grafowe w Coddy.

Teraz przechodzimy przez graf warstwami, używając kolejki.

Wyzwanie

Średni

Teraz zbuduj pełne przejście grafu.

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

Zbuduj listę sąsiedztwa (sąsiedzi posortowani rosnąco), a następnie użyj kolejki: oznacz wierzchołek startowy jako odwiedzony i dodaj go do kolejki, po czym wielokrotnie pobieraj z kolejki wierzchołek, zapisuj go i dodawaj do kolejki jego nieodwiedzonych sąsiadów. Odwiedzane są tylko wierzchołki osiągalne z start.

Spróbuj swoich sił

#include <stdlib.h>

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