Une notion utile pour le calcul des composantes fortement connexe est la notion de point d'attache dont la définition est donnée ci-dessous. Rappelons que l'on suppose les sommets numérotés dans l'ordre où on les rencontre par la procédure de Trémaux.
On remarquera qu'un chemin qui conduit d'un sommet 
à son point
d'attache est ou bien vide (le point d'attache est alors lui
même), ou bien contient une suite d'arcs de 
suivis par un arc
de retour ou un arc transverse. En effet, une succession d'arcs de
partant de conduit à un sommet de numéro plus grand que ,
d'autre part les arcs de descente ne sont pas utiles dans la recherche
du point d'attache, ils peuvent être remplacés par des chemins
formés d'arcs de .
Figure: Les points d'attaches des sommets d'un graphe
Dans la figure 
, on a calculé les points d'attaches
des sommets d'un graphe, ceux-ci ont été numérotés dans
l'ordre où on les rencontre dans l'algorithme de Trémaux; le point
d'attache est indiqué en petit caractère à coté du sommet en
question.
Le calcul des points d'attache se fait à l'aide d'un algorithme récursif qui est basé sur la proposition suivante, dont la preuve est immédiate:
L'algorithme est ainsi une adaptation de l'algorithme de Trémaux, il
calcule at[u] en utilisant la valeur des at[v] pour tous
les successeurs v de u.
var
at: SomVect;
succ: GrapheSuc;
function PointAttache (u: Sommet): Sommet;
var
k: integer;
v, w, mi: Sommet;
begin
k := 1;
v := succ[u, k];
mi := u;
at[u] := u;
while (v <> Omega) do
begin
if (at[v] = Omega) then
w := PointAttache(v)
else
w := v;
mi := Min(mi, w);
k := k + 1;
v := succ[u, k];
end;
at[u] := mi;
PointAttache := mi
end;
for i := 1 to n do
at[i] := Omega;
at[x] := PointAttache(x);
Le calcul des composantes fortement connexes à l'aide des 
est une conséquence du théorème suivant:
Preuve Montrons d'abord que tout sommet de 
appartient
à 
. Soit 
un sommet de , il est extrémité
d'un chemin d'origine 
, prouvons que est aussi extrémité
d'un chemin d'origine . Si tel n'est pas le cas, on peut supposer
que est le plus petit sommet de à partir duquel on ne
peut atteindre , soit 
le chemin joignant à 
, le
chemin obtenu en concaténant à un chemin de 
d'origine
et d'extrémité contient au plus un arc de retour ou
transverse ainsi:
Comme est préfixe, appartient à
et d'après l'hypothèse de minimalité il existe un
chemin d'origine et d'extrémité qui concaténé à
fournit la contradiction cherchée.
Il reste à montrer que
tout sommet 
de appartient aussi à . Un tel sommet est
extrémité d'un chemin 
d'origine , nous allons voir que tout
arc dont l'origine est dans a aussi son extrémité dans
, ainsi tous les sommets de sont dans et en
particulier . Soit 
un arc tel que 
, si 
, 
est un descendant de 
il
appartient donc à 
; si 
alors le chemin menant
de à en passant par contient exactement un arc de
retour ou transverse, ainsi :
et la préfixité de implique 
.
Remarques
est la racine
de on a 
. Si satisfait (ii), alors
l'ensemble 
en entier constitue une composante fortement connexe. Sinon il existe
un descendant de tel que 
. En répétant cet
argument plusieurs fois et puisque le graphe est fini, on finit par
obtenir un sommet satisfaisant les deux conditions.
tel que 
, obtention d'une
composante égale à , suppression de tous les sommets de
et itération des opérations précédentes jusqu'à
obtenir tout le graphe.
, on peut se rendre compte du
procédé de calcul. Il y a 
composantes fortement connexes, les
sommets satisfaisant sont au nombre de 
, il s'agit
de 
. La première composante trouvée se compose du sommet
uniquement, il est supprimé et le sommet 
devient alors tel
que . Tous ses descendants forment une composante
fortement connexe 
. Après leur suppression, le sommet 
satisfait et il n'a plus de descendant satisfaisant la
même relation. On trouve ainsi une nouvelle composante 
.
Une fois celle-ci supprimée 
est le seul sommet qui satisfait la
relation d'où la composante 
. Dans ce cas particulier du sommet , on peut atteindre tous les
sommets du graphe et le calcul s'arrête donc là; en général il
faut reconstruire une arborescence de Trémaux à partir d'un sommet
non encore atteint.
L'algorithme ci-dessous, en Pascal, calcule en même temps
pour tous les descendants de et obtient successivement toutes
les composantes fortement connexes de 
. Il utilise le fait,
techniquement long à prouver mais guère difficile que la
suppression des descendants de lorsque ne modifie pas
les calculs des en cours. La programmation donnée ici
suppose que les sommets ont déjà été numérotés par
l'algorithme de Trémaux à partir de :
var val:array[sommet] of integer;
succ: GrapheSuc;
n:integer;
procedure Supprimer (u: Sommet; nu: integer;
var numComp: SomVect);
(*La suppression d'un sommet s'effectue *)
(*-*)
var
v: Sommet;
k: integer;
begin
numComp[u] := nu;
k := 1;
v := succ[u, k];
while v <> Omega do
begin
if (v > u) and (numComp[v] = 0) then
Supprimer(v, nu, numComp);
k := k + 1;
v := succ[u, k];
end;
end;
procedure PointAttache1 (u: Sommet; var nu: integer;
var at, numComp: Somvect);
var
k: integer;
v, w: Sommet;
begin
at[u] := u; (*Recherche du point d'attache de u*)
k := 1; (*-*)
v := succ[u, k];
while (v <> Omega) do
begin
if (at[v] = Omega) then
begin
PointAttache1(v, nu, at, numComp);
at[u] := Min(at[u], at[v]) (*- *)
end
else if numComp[u] = 0 then
at[u] := Min(at[u], v);
k := k + 1;
v := succ[u, k];
end;
(* - *)
(* - *)
if u = at[u] then
begin
nu := nu + 1;
Supprimer(u, nu, numComp);
end;
end;
procedure CompCon (var numComp: SomVect);
var
k, mi, num: integer;
at: somvect;
u, v, w: Sommet;
begin
for u := 1 to n do
begin
numComp[u] := 0;
at[u] := Omega;
end;
u := 1;
num := 0;
for u := 1 to n do
if ((numComp[u]) = 0 and (at[u] = Omega)) then
PointAttache1(u, num, at, numComp)
end;