Accueil ⇒ Informatique ⇒ Algorithmique ⇒ Circuit Eulérien

Circuit Eulérien

Pseudo code

Pré-requis

Pour que l'algorithme soit applicable, il faut que le graphe soit connexe et que tous les degrés des noeuds soient pairs. On supposera la parité contrôlé dès la lecture des données ; quant à la connexité, on peut la vérifier avec un DFS, ou contrôler que tous les noeuds apparaissent dans le circuit résultant.

Données

On suppose que tous les M arcs sont numérotés de 0 à (M - 1). On créé un tableau de booléen global arcLibre initialisé à VRAI.

En sortie, on considère une pile Circuit qui comportera la liste des noeuds du circuit, dans l'ordre de parcours.

Algorithme 

ConstruireCircuit(noeud n)
    Pour chaque voisin v de n
        Soit a l'arc (n, v) de numéro k
        Si arcLibre[k]
            arcLibre[k] = FAUX
            ConstruireCircuit(v)
    Circuit.empiler(n)

Nuances

Dans le cas d'une matrice d'adjacence, on peut stocker le nombre d'arcs entre deux noeuds et le décrémenter à chaque appel, en lieu et place du tableau de booléens arcLibre.