Je cherche un algorithme qui me dirait s'il est possible de parcourir toutes les arêtes d'un graphe unidirectionnel une seule fois. L'algorithme devrait être capable de partir de n'importe quel nœud et de parcourir l'ensemble du graphe sans repasser par la même arête.
Réponses
Trop de publicités?
Rob Kennedy
Points
107381
Ce que vous recherchez s'appelle un Trajectoire eulérienne et Wikipedia décrit quelques algorithmes pour en construire un, si votre graphique remplit les conditions nécessaires.
Brian Cain
Points
7150
En Les sept ponts de Königsberg est un exemple classique de chemin eulérien.
Algorithme de Hierholzer, de Wikipédia :
Choisissez n'importe quel sommet de départ jusqu'à ce qu'elle revienne à v. Il n'est pas possible de rester bloqué à un autre autre sommet que v, car le degré pair de tous les sommets garantit que, lorsque la piste entre dans un autre sommet w, il doit y avoir une arête inutilisée qui quitte w. Le circuit ainsi formé est un circuit fermé, mais il est possible qu'il ne soit pas bloqué. pas couvrir tous les sommets et toutes les arêtes du graphe initial.
A il existe un sommet v qui appartient à la tournée en cours mais qui a des arêtes adjacentes ne faisant pas partie de la tournée, commencer une autre piste à partir de v, en suivant les arêtes inutilisées jusqu'à ce qu'on revienne à v, et rejoindre la tournée formée ainsi formée à la tournée précédente.
En utilisant une structure de données telle qu'un liste doublement chaînée pour maintenir l'ensemble des arêtes inutilisées incidentes à chaque sommet, pour maintenir la liste des sommets de la tournée en cours qui qui ont des arêtes inutilisées, et pour gérer la tournée elle-même, l'opérateur individuel de l'algorithme (recherche des arêtes inutilisées sortant de chaque sommet, trouver un nouveau sommet de départ pour une tournée, et relier deux tournées qui partagent un sommet) peuvent être effectuées chacune en temps constant, de sorte que l'algorithme l'algorithme global prend donc un temps linéaire.
