Algorithme de Tarjan

function CC = tarjan(G)
 
S = []; %pile
CC = []; %toutes les composantes fortement connexes
index = zeros(1, size(G,1)); %date de découverte du sommet (rang)
index_accessible = zeros(1, size(G,1)); %rang d'attache du sommet
idx = 1;
 
% Parcours des sommets non marqués
for i = 1 : size(G,1)
    if(index(i) == 0)
        [CC S idx index index_accessible] = strongconnect(CC, G, i, S, idx, index, index_accessible);
    end
end
end
 
function [C S idx index index_accessible] = strongconnect(C, G, v, S, idx, index, index_accessible)
index(v) = idx;
index_accessible(v) = idx;
idx = idx+1;
S = push(S,v); %ajouter le sommet courant à la pile
 
% Liste les sommets adjacents au sommet courant
n = voisin(G,v);
 
% Parcours récursif
for i = 1:length(n)
    if(index(n(i)) == 0)
        [C, S idx index index_accessible] = strongconnect(C, G, n(i), S, idx, index, index_accessible);
        index_accessible(v) = min(index_accessible(v), index_accessible(n(i)));
    elseif (~isempty(find(S == n(i), 1)))
        index_accessible(v) = min(index_accessible(v), index(n(i)));
    end
end
 
% Le sommet est une racine, on calcule la composante fortement connexe associée
if(index_accessible(v) == index(v))
    cc = []; %composante fortement connexe issue du sommet
    if(~isempty(S))
        [tmp S] = pop(S);
        cc = [cc tmp];
    end
    while(~isempty(S) && tmp ~= v)
        [tmp S] = pop(S);
        cc = [cc tmp];
    end
    if(~isempty(cc))
        % Les composantes connexes n'ont pas toutes
        % la même longueur. On complète donc la ligne
        % avec des 0.
        C = [C ; cc zeros(1,size(G,1) - length(cc))];
    end
end
end
 
function V = voisin(G,s)
V = find(G(s,:)==1);
end
 
% empiler
function p = push(p, n)
p = [p n];
end
 
% dépiler
function [n, p] = pop(p)
n = [];
if(~isempty(p))
    n = p(end);
    p = p(1:end-1);
end
end