Implementacja (część 1)
Lekcja 5 z 9 w kursie Algorytm Prima – algorytmy grafowe w Coddy.
Zaczynamy od najtańszej krawędzi wychodzącej z wierzchołka — to pierwszy ruch Prima.
Wyzwanie
ŁatwyPierwszym krokiem algorytmu Prima jest sprawdzenie krawędzi wychodzących z wierzchołka początkowego. Przygotujmy funkcję wyszukującą takie krawędzie.
Napisz funkcję o nazwie minEdgeFrom, która przyjmuje płaską tablicę edges (trójki [u, v, w, ...], graf nieskierowany) oraz wierzchołek node i zwraca najmniejszą wagę spośród wszystkich krawędzi przylegających do node. Jeśli node nie ma żadnych krawędzi, zwróć -1.
Na przykład minEdgeFrom([0,1,5, 0,2,3, 1,2,1], 0) zwraca 3.
Spróbuj swoich sił
#include <stdlib.h>
int minEdgeFrom(int* edges, int edges_size, int node) {
// Napisz kod tutaj
return -1;
}
Sprawdź sięTa lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.
Wszystkie lekcje w sekcji Algorytm Prima – algorytmy grafowe
2Algorytm
Jak to działa?PseudokodImplementacja (część 1)Implementacja (część 2)
Złożoność czasowa i pamięciowaPoćwicz samodzielnie: Kompilator C online