Implementacja (część 2)

Lekcja 6 z 9 w kursie Algorytm Kruskala — algorytmy grafowe w Coddy.

Teraz dodaj najtańszą bezpieczną krawędź, aż drzewo MST będzie kompletne.

Wyzwanie

Średni

Teraz zbuduj MST.

Napisz funkcję o nazwie kruskal, która przyjmuje n oraz płaską tablicę edges (trójki, graf nieskierowany) grafu spójnego i zwraca całkowitą wagę jego minimalnego drzewa rozpinającego.

Wielokrotnie wybieraj najtańszą niewykorzystaną krawędź; jeśli jej końce należą do różnych zbiorów, połącz je i dodaj jej wagę; w przeciwnym razie pomiń ją.

Wykorzystaj ponownie pomysł z użyciem struktury union-find z poprzedniej lekcji.

Spróbuj swoich sił

#include <stdlib.h>

int kruskal(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 Kruskala — algorytmy grafowe

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

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

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

3Wyzwania końcowe

Wyzwanie końcowe #1 Wyzwanie końcowe #2

Poćwicz samodzielnie: Kompilator C online