Algorithme de Kruskal

function [T w] = kruskal(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
 
CC = zeros(size(G));
for i = 1 : size(G,1)
    CC(i,i) = 1;
end
 
for i = 1 : naretes
    [tmp, u] = min(H);
    [~, v] = min(tmp);
    u = u(v);
    if(~isequal(CC(u,:), CC(v,:)))
    % Si les deux composantes connexes sont différentes alors on les
    % fusionne
        CC(u, CC(v,:) == 1) = 1;
        cc = find(CC(u,:)==1);
        for j = 1 : length(cc)
            CC(cc(j), :) = CC(u,:);
        end
        T(u,v) = 1;
        T(v,u) = 1;
    end
    H(u,v) = inf;
    H(v,u) = inf;
end
w = sum(G(T == 1)) / 2;
end