|
private static Lifo stack ; private static int doFindBiconnect (int s, int pere) { int lowpt ; ++numOrder ; lowpt = num[s] = numOrder ; for (List p = succ[s] ; p != null ; p = p.next) { int n = p.val ; if (num[n] == 0) { stack.push(new Edge(s,n)) ; int lowN = doFindBiconnect(n, s) ; lowpt = Math.min(lowN,lowpt) ; if (lowN >= num[s]) { System.out.print("Composante : " + s ) ; Edge e = stack.pop () ; while (num[e.src] >= num[n]) { System.out.print(" " + e) ; e = stack.pop() ; } System.out.println(" " + e) ; } } else if (num[n] < num[s] && n != pere) { stack.push(new Edge(s,n)) ; lowpt = Math.min(num[n],lowpt) ; } } return lowpt ; } static void findBiconnect(int s) { numOrder = 0 ; num = new int[succ.length] ; stack = new Lifo () ; doFindBiconnect(s,s) ; } |
L'idée est d'abord d'empiler les arcs du palmier. L'affichage des composantes est en fait assez simple : juste après un appel récursif, tous les arcs visités durant l'appel ont été empilés et plus aucun arc concernant les sommets visités ne sera empilé.
Prenons le cas de
s point d'articulation, possédant un
seul fils, et dont aucun descendant dans l'arbre n'est un point
d'articulation, les arcs de la
composante sont alors sur la pile, du sommet au dernier arc empilé avant
l'appel récursif. Ce dernier arc est le premier à partir du haut dont
le numéro de la source est inférieur au numéro de n (de fait c'est s).Dans le cas de
s point d'articulation, possédant deux
sous-arbres dont l'un est une composante, on voit que la
méthode doFind rendra une pile contenant les arcs du
sous-arbre qui n'est pas la composante et ceci que la composante soit
parcourue en premier ou en second.R. Tarjan propose une preuve utilisant à proprement parler l'induction sur le nombre de composantes biconnexes, et reposant au final sur les remarques ci-dessus.