BFS
Lekcja 10 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Kolejne wyzwania mają na celu wykorzystanie klasy Graph, którą właśnie utworzyłeś.
W każdym wyzwaniu otrzymujesz zablokowany plik graph (końcowy Graph z poprzedniego rozdziału) oraz nowy plik solution, w którym napiszesz funkcję korzystającą z Graph.
Nasz pierwszy algorytm: przeszukiwanie wszerz. Rozpoczynając od wierzchołka, BFS odwiedza wszystkie osiągalne wierzchołki falami: najpierw wierzchołek początkowy, potem wszystkie wierzchołki oddalone o jedną krawędź, następnie o dwie krawędzie i tak dalej. Klasyczna implementacja wykorzystuje kolejkę: dodaj wierzchołek początkowy do kolejki, a następnie wielokrotnie pobieraj z niej wierzchołek, oznaczaj go jako odwiedzony i dodawaj do kolejki wszystkich nieodwiedzonych sąsiadów.
Ponieważ listy sąsiadów nie mają ustalonej kolejności, dwa poprawne przebiegi BFS mogą dać różne kolejności przechodzenia. Aby w tym wyzwaniu wynik był deterministyczny, posortuj sąsiadów każdego wierzchołka rosnąco przed dodaniem ich do kolejki.
Wyzwanie
ŁatwyNapisz funkcję bfs, która otrzymuje dwuwymiarową tablicę liczb całkowitych adjacency (każdy wiersz to krawędź [u, v]) oraz liczbę całkowitą start i zwraca kolejność odwiedzania w BFS od start jako listę liczb całkowitych.
Zbuduj graf: dla każdej krawędzi [u, v] w adjacency wywołaj g.addEdge(u, v). Następnie wykonaj BFS od start, używając kolejki. Podczas przetwarzania sąsiadów wierzchołka posortuj ich rosnąco, aby wynik był deterministyczny.
Musisz użyć klasy Graph (dostępnej w graph) — nie używaj wbudowanych typów języka (map, zbiorów) do reprezentowania sąsiedztwa. Dane pomocnicze algorytmu (zbiory odwiedzonych wierzchołków, kolejki) mogą korzystać ze standardowych typów bibliotecznych.
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 = bfs(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