Algorithme de Prim

% GraphTook - 2007-2012 Glotin & Chouchane
% Dyni LSIS USTV - {glotin, mathieu.chouchane} @ univ-tln.fr
 
function [T w] = prim(G)
 
ordre = size(G,1);
H = (G > 0);
T = zeros(size(G));
 
parent = zeros(1, ordre);
cle = inf * ones(1, ordre);
visite = zeros(1, ordre);
 
% On choisit un sommet de depart au hasard, la racine
s = alea(ordre);
% cle(s) : poids minimal d'une arete reliant s un sommet de l'arbre     
cle(s) = 0;
% comme s est la racine de l'arbre, cle(s) = 0
visite(s) = 1;
% L'algorithme de Prim effectue n iterations, n etant le nombre de sommets
% du graphe
while(sum(visite) ~= ordre)
    [~, s] = min(cle);
    % On cherche l'arete de poids minimal et on la marque
    cle(s) = inf;
    visite(s) = 1;
    % Si s a un parent dans l'arbre on ajoute l'arete a l'arbre couvrant
    if(parent(s) ~= 0)
        T(s, parent(s)) = 1;
        T(parent(s), s) = 1;
    end
    v = voisin(H, s);
    % Mise à jour des vecteurs cle et parent
    for i = 1 : length(v)
        if(visite(v(i)) == 0 && G(s,v(i)) < cle(v(i)))
            parent(v(i)) = s;
            cle(v(i)) = G(s, v(i));
        end
    end
end
 
% Calcul du poids de l'arbre couvrant
w = sum(G(T == 1)) / 2;
 
end
 
function zs = alea(n)
aux=randperm(n);
zs=aux(1);
end
 
function V = voisin(G,s)
V = find(G(s,:) == 1);
end