Implementacja (część 2)
Lekcja 6 z 9 w kursie Algorytm Prima – algorytmy grafowe w Coddy.
Teraz rozbuduj drzewo, zawsze dodając najtańszą krawędź przecinającą.
Wyzwanie
ŚredniTeraz rozbuduj całe drzewo.
Napisz funkcję o nazwie prim, która przyjmuje n i płaską tablicę edges (trójki, graf nieskierowany) grafu spójnego i zwraca całkowitą wagę minimalnego drzewa rozpinającego, zaczynając budować drzewo od wierzchołka 0.
Dla każdego wierzchołka przechowuj flagę inTree. W każdej rundzie znajdź najtańszą krawędź, której dokładnie jeden koniec należy do drzewa, dodaj jej wagę i dołącz do drzewa jej drugi koniec.
Spróbuj swoich sił
#include <stdlib.h>
int prim(int n, int* edges, int edges_size) {
// Napisz kod tutaj
return 0;
}
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