RO03 - Recherche opé ...

Recherche en largeur (Breadth-First Search)

- Un parcours en largeur d’un graphe G :

• Visite tous les sommets et toutes les arêtes de G,
• Détermine si G est connexe ou non,
• Calcule les composantes connexes de G,
• Calcule une forêt couvrante pour G.

- La complexité en temps d’un parcours en largeur est O(n+m).

- L’algorithme de parcours en largeur peut être modifié pour résoudre d’autres problèmes sur les graphes:

• Trouver et retourner un chemin de longueur minimale entre deux sommets,
• trouver un cycle simple, s’il y en a un.

de: http://www.iro.umontreal.ca/~hamelsyl/recherche.pdf