1. Et voilà, en utilisant, num passé en argument et rendu en résultat. Une variable globale (statique) fait tout aussi bien l'affaire.
      static private int doPrefix (int s, int num, boolean [] vu) {

            if (vu[s]) return num ;
        vu[s] =     true ;
        System.out.print(" " + s + ":" + num) ; num++ ;
            for (List p = succ[s] ; p != null ; p = p.next) {
          num = doPrefix(p.val, num, vu) ;
        }
            return num ;
      }

          static void prefix(int s) {
            boolean [] vu = new boolean [succ.length] ;

        doPrefix(s,0,vu) ; System.out.println() ;
      }


  2. Et voilà :
      static private int doSuffix (int s, int num, boolean [] vu) {

            if (vu[s]) return num ;
        vu[s] =     true ;
            for (List p = succ[s] ; p != null ; p = p.next) {
          num = doSuffix(p.val, num, vu) ;
        }
        System.out.print(" " + s + ":" + num) ; num++ ;
            return num ;
      }

          static void suffix(int s) {
            boolean [] vu = new boolean [succ.length] ;

        doSuffix(s,0,vu) ; System.out.println() ;
      }
    La seule différence est que les numéros sont attribués après le parcours récursif des voisins.

  3. C'est un peu gratuit. Une solution possible est de marquer les sommets comme vus à la sortie de la pile.
      private static void xbfs(int s) {
            Lifo stack = new Lifo () ;
            boolean [] vu = new boolean[succ.length] ;

        stack.add(s) ; stack.add(s) ;
            do {
              int n = stack.get () ;
              int pere = stack.get () ;
              if (!vu[n]) {
            vu[n] =     true ;
            System.out.print(" " + n + "<" + pere + ">") ;
                for (List p = succ[n] ; p != null ; p = p.next) {
              stack.add(n) ; stack.add(p.val) ;
            }
          }
        }     while (!stack.isEmpty()) ;
      }
    On notera que la pile est utilisée pour se souvenir du père de chaque sommet empilé.

    Par ailleurs, la terminaison devient un peu plus subtile. Il suffit de considérer la couple d'entiers (V-nv, ns) où V est le nombre de sommets du graphe, nv est le nombre de sommets vus et ns la taille de la pile. Alors, du début à la fin d'une itération, ce couple décroît strictement pour l'ordre lexicographique sur les paires d'entiers naturels. Si cette explication choque un peu, considérer l'entier 2V(V-nv) + ns, strictement décroissant.