% GraphTook - 2007-2012 Glotin & Chouchane
% Dyni LSIS USTV - { glotin, mathieu.chouchane} @ univ-tln.fr

function [T w] = kruskal_cours(G)
% T : matrice d'adjacence de l'arbre couvrant trouvé
% w : poids de l'arbre couvrant

T = zeros(size(G));

H = (G > 0);

naretes = sum(sum(H));

% On passe le poids des arêtes de poids nul à inf
H = G;
H(H == 0) = inf;

% Pour trouver un arbre couvrant, il faut au moins une composante connexe
% dans le graphe
if(isempty(tarjan(G)))
    return;
end

for i = 1 : naretes
    [tmp, u] = min(H);
    [~, v] = min(tmp);
    u = u(v);
    % On ajoute l'arête à l'arbre
    T(u,v) = 1;
    T(v,u) = 1;
    p = size(tarjan(T),1);
    m = sum(sum(T)) / 2;
    n = size(T,1);
    % Formule d'Euler
    if(m - n + p > 0)
        % Si on détecte un cycle, on enlève l'arête précédemment ajoutée
        T(u,v) = 0;
        T(v,u) = 0;
    end
    H(u,v) = inf;
    H(v,u) = inf;
end
% Calcul du poids de l'arbre couvrant
w = sum(G(T == 1)) / 2;
end
