Końcowe wyzwanie nr 1

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

Wyzwanie

Średni

Czas na klasyczne zastosowanie BFS.

Napisz funkcję o nazwie shortestPath, która przyjmuje n, płaską tablicę edges (graf nieskierowany), wierzchołek start i wierzchołek target, a następnie zwraca długość najkrótszej ścieżki (liczbę krawędzi) od start do target. Jeśli nie można dotrzeć do target, zwróć -1.

Na przykład na ścieżce 0-1-2-3 najkrótsza ścieżka od 0 do 3 ma długość 3.

Spróbuj swoich sił

#include <stdlib.h>

int shortestPath(int n, int* edges, int edges_size, int start, int target) {
    // Napisz kod tutaj
    return -1;
}

Wszystkie lekcje w sekcji Przeszukiwanie wszerz — algorytmy grafowe

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

Jak to działa?Pseudokod Implementacja (część 1)Implementacja (część 2)

Złożoność czasowa i pamięciowa

3Końcowe wyzwania

Końcowe wyzwanie nr 1Końcowe wyzwanie nr 2

Poćwicz samodzielnie: Kompilator C online