Parcours de graphe Plan du cours Une stratégie possible

Bogdan

Description

Parcours de graphe Plan du cours Une stratégie possible

Sujets

• cours

Informations

• Publié par: axovemiw
• Nombre de lectures: 104
• Langue: Français

Extrait

148 / 187

Parcours de graphe

149 / 187

Plan du cours

Graphes non-valués, orientés ou non-orientés,

– parcours de graphe (exploration: visiter tous les

nœuds)

– recherche dans un graphe (trouver un chemin entre

s

et

d

)

Beaucoup d’applications, briques de base pour

algorithmes de graphes

– exemple: trouver les composante fortement connexes

d’un graphe orienté

150 / 187

Comment on explore un labyrinthe?

•

Peut-on aller de

s

à

d

?

•

Le chemin le plus court?

151 / 187

Une stratégie possible

ParcoursLabyrinthe(c)

si

c != d

marquer

c

comme visité

pour chaque carré

c’

adjacent à

c

si

c’

n’est pas visité

ParcoursLabyrinthe(c’)