36. Introduction aux Graphes

Un Graphe est une structure de données non linéaire utilisée pour modéliser les relations entre les objets. Il se compose d'un ensemble de Vertices (V) (ou nœuds/sommets) et d'un ensemble d'Edges (E) (ou connexions/arêtes).

Types de Graphes

1. Graphe Non Orienté (Undirected Graph) : Les arêtes n'ont pas de direction. Si A est connecté à B, B est également connecté à A (par exemple, les amitiés sur Facebook).
2. Graphe Orienté (Directed Graph / Digraph) : Les arêtes ont une direction. Une connexion de A à B n'implique pas une connexion de B à A (par exemple, les abonnés Twitter).
3. Graphe Pondéré (Weighted Graph) : Les arêtes ont des valeurs numériques (poids) qui leur sont attribuées, représentant le coût, la distance ou le temps (par exemple, les distances d'un réseau routier).
4. Cyclique vs. Acyclique : Un cycle est un chemin qui commence et se termine au même sommet. Un graphe sans cycles est acyclique (comme un arbre).

Les graphes sont utilisés pour modéliser tout, des réseaux de transport aux liens de sites Web et aux dépendances complexes.