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

最終更新日時: 2014年 07月 7日(月曜日) 22:25