Wprowadzenie

Witaj na ostatnim kursie z serii Algorytmy grafowe! Podobnie jak algorytm Kruskala, algorytm Prima tworzy minimalne drzewo rozpinające: najtańszy zbiór krawędzi, który łączy każdy wierzchołek i nie zawiera cyklu. Oba algorytmy dochodzą do tego samego wyniku, ale różnymi drogami.

Algorytm Prima rozbudowuje drzewo na zewnątrz, zaczynając od wybranego wierzchołka. W każdym kroku dodaje pojedynczą najtańszą krawędź, która łączy drzewo z wierzchołkiem, który jeszcze do niego nie należy.

Graf jest nieskierowany i ważony. Jest podany jako n (wierzchołki od 0 do n - 1) oraz edges, płaska tablica trójek [u0, v0, w0, ...], reprezentujących nieskierowaną krawędź u - v o wadze w. Zaczynamy od wierzchołka 0.

Dokończmy serię!