Graphes : Définitions et Parcours

Les graphes sont des structures de données fondamentales permettant de modéliser des réseaux (Internet, réseaux sociaux, transports) ou des relations complexes.

1. Définitions fondamentales

  • Sommets (Nodes) : Les points du graphe.
  • Arêtes (Edges) : Les liens entre les sommets (graphe non-orienté).
  • Arcs : Les liens fléchés (graphe orienté).
  • Dégre : Nombre de voisins d'un sommet.
  • Ordre : Nombre total de sommets.
  • Taille : Nombre total d'arêtes ou d'arcs.

2. Représentations en machine

Il existe deux méthodes principales pour coder un graphe en Python :

A. Matrice d'adjacence

Un tableau 2D (liste de listes) où M[i][j] = 1 si un lien existe entre i et j.

B. Listes d'adjacence

Un dictionnaire où chaque clé est un sommet et la valeur est la liste de ses voisins.

graphe = { 'A': ['B', 'C'], 'B': ['A', 'D'], ... }

3. Parcours de graphes

Pour explorer un graphe, on utilise deux algorithmes classiques :

Parcours en Largeur (BFS - Breadth First Search)

Explore étage par étage. Utilise une FILE (FIFO).

Parcours en Profondeur (DFS - Depth First Search)

Explore une branche jusqu'au bout avant de revenir. Utilise une PILE (LIFO) ou la récursivité.

Exercices de compréhension (10 questions)

QCM : Test de validation

Challenge : Analyse de Graphe Dynamique

Voici un graphe généré aléatoirement. Répondez aux 10 questions d'analyse ci-dessous.