Définition
Graphe
Un graphe est une structure composée de nœuds (ou sommets) connectés par des arêtes (ou arcs).
Sommet
Un sommet est un point ou un nœud dans un graphe.
Arête
Une arête est une connexion entre deux sommets dans un graphe.
Graphe orienté
Un graphe où les arêtes ont une direction, allant d'un sommet à un autre.
Graphe non orienté
Un graphe où les arêtes n'ont pas de direction.
Parcours en largeur
Un algorithme de parcours de graphe qui explore tous les voisins d'un sommet avant de passer au niveau suivant.
Parcours en profondeur
Un algorithme de parcours de graphe qui explore un chemin complet à partir d'un sommet avant de revenir en arrière.
Représentation des graphes en Python
En Python, les graphes peuvent être représentés de plusieurs manières, mais deux des méthodes les plus courantes sont l'utilisation de listes d'adjacence et de matrices d'adjacence.
Liste d'adjacence
Une liste d'adjacence est une façon d'encoder un graphe où chaque sommet a une liste contenant ses sommets adjacents. En Python, cela peut être implémenté à l'aide d'un dictionnaire avec des listes.
Exemple de code :
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}Parcours en largeur (BFS)
Le parcours en largeur commence au sommet de départ et explore tous ses voisins avant de se déplacer à un niveau plus profond.
Exemple de code en Python :
def bfs(self, depart): visite = [] file = [depart] while file: sommet = file.pop(0) if sommet not in visite: visite.append(sommet) print(sommet, end=" ") for voisin in self.adjacence[sommet]: if voisin not in visite: file.append(voisin)
Parcours en profondeur (DFS)
Le parcours en profondeur explore autant qu'il le peut le long de chaque branche avant de reculer. Il peut être implémenté de manière récursive ou avec une pile.
Exemple de code en Python (avec récursion) :
def parcours_profondeurs(self,u,visite = None):
if visite is None :
visite = []
if u not in visite :
visite.append(u)
visite.append("->")
nonvisite = [v for v in self.adj[u] if v not in visite]
for v in nonvisite :
self.parcours_profondeurs(v,visite)
return visite
A retenir :
Les graphes sont des structures utilisées pour modéliser des relations entre des objets. En Python, nous pouvons représenter des graphes à l'aide de listes d'adjacence ou de matrices d'adjacence. Les parcours en largeur (BFS) et en profondeur (DFS) sont essentiels pour naviguer et explorer ces structures de données. BFS utilise une file pour suivre les sommets à visiter, tandis que DFS utilise une approche récursive ou une pile. Chacune de ces méthodes a ses propres applications et avantages en fonction de la structure du problème à résoudre.
