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) ; } |
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).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.