La théorie des graphes est une branche des mathématiques et de l'informatique qui étudie les relations entre des objets. En programmation, elle s'applique à la modélisation et à la résolution de problèmes impliquant des réseaux ou des structures de données interconnectées.
Un graphe se compose de nœuds (ou sommets) reliés par des arêtes (ou liens). Ces éléments peuvent représenter divers concepts, tels que des villes reliées par des routes, des utilisateurs dans un réseau social, ou des pages web connectées par des hyperliens.
Les algorithmes de théorie des graphes sont utilisés pour :
- Parcourir des graphes (ex : recherche en profondeur, recherche en largeur)
- Trouver le chemin le plus court entre deux nœuds (ex : algorithme de Dijkstra)
- Détecter des cycles ou des composantes connexes
- Résoudre des problèmes d'optimisation (ex : problème du voyageur de commerce)
Exemple pratique en Python :
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=" ")
for neighbour in self.graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# Utilisation
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("Parcours en largeur (en partant du sommet 2):")
g.bfs(2)La théorie des graphes trouve des applications dans de nombreux domaines, comme les réseaux de transport, les systèmes de recommandation, l'analyse de réseaux sociaux, ou encore l'optimisation de bases de données. Elle est également liée à d'autres concepts en informatique, tels que les arbres, les structures de données et la complexité algorithmique.
