Algorithme de Kruskal

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