TNSI : Parcours en Largeur ou BFS - Breadth First Search

Introduction

Introduction (+ Lien avec la notion de plus courts chemins dans un Graphe) (12 min 54)

Parcours en Largeur avec une File

Parcours en Largeur avec File (28 min 58)

Résumé

Un Parcours en Largeur ou BFS - Breadth First Search :

• peut être implémenté avec des Files
• Détermine si le graphe est Connexe, ou pas
• Détermine si le graphe admet un Cycle, ou pas
• fonctionne pour des Graphes Orientés, ou Non Orientés
• ne fonctionne QUE pour des graphes NON pondérés, à priori, mais:
• admet une généralisation dans un Graphe Pondéré:
  • à poids \(>0\), Orienté ou Non : qui est alors appelé un Algorithme de Dijkstra (cf TD) (Edsger Dijkstra, 1959)
  • pour des poids quelconques (\(>0\) ou \(<0\)), Orienté : grâce à l'Algorithme de Floyd-Warshall (article en 1962), encore appelé Algorithme de Roy-Floyd-Warshall (car énoncé par Bernard Roy en 1959)
• Construit un Arbre Couvrant (pas forcément minimal)
• Construit un Arbre des plus courts chemins entre un sommet de départ et tous les autres sommets (atteignables), dans un graphe non pondéré
• Construit un chemin entre un sommet de départ et tous les autres sommets (atteignables), dans un graphe non pondéré