Utilisateur:Fschwarzentruber/Brouillon

Donnons maintenant le pseudo-code de l'algorithme (voir Algorithm 2.3.1 dans ^[1]) :

entrée : un graphe G, sommet départ s
sortie : un chemin eulérien partant de s, s'il y en a un effet de bord : on supprime toutes les arêtes de G
fonction Euler(G, s)

     L = vide (liste des sommets du parcours qui ont encore des arêtes inutilisées)
     pour tout sommet v, utilisé[v] := faux
     pour tout arête e, nouvelle[e] := vrai

     entrée : sommet s
     sortie : un cycle de s à s
     fonction extraire(s)
         C = vide
         v := s
         tant que v possède une arête adjacente dans G
              supprimer de G une arête e adjacente à s
              si nouvelle(e) alors
                    ajouter e à la fin de C
                    nouvelle[e] = faux
                    v := autre extrémité de e
                    si non utilisé[v] alors
                            ajouter v à L
                            utilisé[v] := true
         renvoyer C

     s := choisir un sommet dans G
     utilisé[s][:= true
     ajouter s à L
     K := extraire(s)

     tant que L est non vide
            u:= défiler le dernier élément de L
            C := extraire(u)
            insérer C devant e(u) dans K

↑ (en) Dieter Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, coll. « Algorithms and Computation in Mathematics », 2008 (ISBN 978-3-642-09186-5, lire en ligne)

[1] (en) Dieter Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, coll. « Algorithms and Computation in Mathematics », 2008 (ISBN 978-3-642-09186-5, lire en ligne)

[1]