Représentation des graphes et parcours (en largeur, en profondeur)

En 30 secondes

• Un graphe est représenté par une matrice d'adjacence (tableau) ou une liste d'adjacence (voisins de chaque sommet).
• Le parcours en largeur visite niveau par niveau avec une file ; le parcours en profondeur explore un chemin jusqu'au bout avec une pile.
• Les deux parcours visitent tous les sommets accessibles, mais dans un ordre différent dès qu'un sommet a plusieurs chemins d'accès.

Ce que tu sauras faire

• Représenter un graphe par une matrice d'adjacence et par une liste d'adjacence.
• Dérouler un parcours en largeur (BFS) sur un graphe à partir d'un sommet donné.
• Dérouler un parcours en profondeur (DFS) sur un graphe à partir d'un sommet donné.

Les mots à connaître

Graphe

un ensemble de sommets reliés entre eux par des arêtes (graphe non orienté) ou des arcs (graphe orienté), représentant des relations entre des objets.

Sommet

chacun des éléments reliés entre eux dans un graphe, aussi appelé nœud.

Arête / Arc

le lien qui relie deux sommets d'un graphe ; une arête n'a pas de sens de parcours (graphe non orienté), un arc va d'un sommet vers un autre selon un sens précis (graphe orienté).

Le piège classique

Confondre le parcours en largeur et le parcours en profondeur : le premier utilise une file (visite niveau par niveau), le second utilise une pile (explore un chemin jusqu'au bout avant de revenir en arrière).

L'astuce

Parcours en LARGEUR = file (FIFO), niveau par niveau ; parcours en PROFONDEUR = pile (LIFO), un chemin jusqu'au bout puis retour en arrière.