Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====Chercher une chaine dans un graphe====
Ici nous cherchons à connaitre le chemin entre deux noeuds\\
:!: cet algorithme renvoie un chemin, ce n'est pas forcement le plus court \\
L'algorithme va renvoyer une chaine de noeud entre le __noeud de depart__ et le __noeud d'arrivé__

<code>
VARIABLE
G : un graphe
start : noeud (noeud de départ)
end : noeud (noeud d'arrivé)
u : noeud
chaine : ensemble de noeuds (initialement vide)

DEBUT
TROUVE-CHAINE(G, start, end, chaine):
  chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d'ajouter le noeud start à l'ensemble chaine
  si start est identique à end :
    renvoie chaine
  fin si
  pour chaque sommet u adjacent au sommet start :
    si u n'appartient pas à chaine :
      nchemin = TROUVE-CHAINE(G, u, end, chaine)
      si nchemin non vide :
        renvoie nchemin
      fin si
    fin si
	fin pour
	renvoie NIL
FIN
</code>

Wiki NSI

Outils pour utilisateurs

Outils du site

Outils de la page