Implementacja algorytmu Prima

Witam,

Mam drobny problem z implementacją w/w algorytmu w języku C++, otóż przeszukałem już masę stron, ale nadal nie do końca rozumiem jak go zaimplementować i prosiłbym o jakąś pomoc.

Głównie opieram się na: http://www.algorytm.org/algorytmy-grafowe/algorytm-prima.html

Mam do wykonania pewne zadanie, w którym, krótko mówiąc mam wyznaczyć najmniejsze drzewo rozpinające oraz wyświetlić jego krawędzie.
Tutaj małe ale, musi być to implementacja macierzowa bo złożoność ma być n^2, więc odpadają kopce i inne cuda.

Obecnie zabrałem się do tego w taki sposób:

Mam sobie trzy macierze, macierz sąsiedztwa krawędzi(2 wymiary), macierz wag krawędzie( 1 wymiar) i macierz odwiedzonych już krawędzi(2 wymiary). Później sortuję sobie macierz sąsiedztwa i macierz wag od wartości najmniejszej do największej po czym w dwóch pętlach próbuję przeszukiwać tak macierz żeby wyświetlić właściwe krawędzie, ale z tym jest problem, bo nie bardzo rozumiem jak się do tego zabrać.

Prosiłbym o jakąś radę.

Pozdrawiam

1. Wybierasz dowolny wierzchołek - zaznaczasz jako wybrany.
2. W pętle dopóki liczba wybranych mniejsza niż ilość wierzchołków
   2.1. Znajdujesz krawędź łącząca jeden z wybranych węzłów z jednym z niewybranych.
   2.3. Wybierasz znalezioną krawędź.
   2.4. Wybierasz ten nie wybrany węzeł z tej wybranej krawędzi.
   2.5. koniec pętli