Les graphes : comprendre les bases

Tu peux voir un graphe comme un réseau constitué de points (appelés nœuds ou sommets) reliés par des lignes (les arêtes ou arcs). C'est comme une carte où les villes seraient les nœuds et les routes les arêtes !

Il existe deux types principaux de graphes. Dans un graphe orienté, les relations ont un sens précis - imagine une rue à sens unique. Les connexions s'appellent alors des arcs et sont représentées par des couples ordonnés de sommets.

À l'inverse, un graphe non-orienté fonctionne comme une rue à double sens. Ici, on parle d'arêtes qui relient simplement deux sommets sans notion de direction particulière.

💡 Astuce : Pour retenir la différence, pense aux réseaux sociaux ! Sur Twitter, tu peux suivre quelqu'un sans qu'il te suive (graphe orienté), tandis que sur Facebook, l'amitié est réciproque $graphe non-orienté$.

Propriétés des graphes et algorithmes essentiels

Une boucle est un cas particulier où un sommet se relie à lui-même - comme quelqu'un qui se suit sur les réseaux sociaux ! Le degré d'un sommet dans un graphe non-orienté correspond au nombre d'arêtes qui le touchent.

Pour les graphes orientés, c'est un peu plus complexe. Le degré sortant compte combien d'arcs partent du sommet, tandis que le degré entrant compte ceux qui y arrivent.

Les algorithmes de parcours te permettent d'explorer tous les sommets d'un graphe. Tu peux parcourir en largeur (explorer tous les voisins avant d'aller plus loin) ou en profondeur (aller le plus loin possible avant de revenir en arrière).

Pour trouver le chemin le plus court, plusieurs algorithmes existent comme Dijkstra, Bellman-Ford ou Floyd-Warshall. Chacun a ses avantages selon le type de problème !

🎯 Bon à savoir : L'algorithme de Dijkstra est parfait pour les GPS - il trouve toujours le chemin le plus rapide entre deux points !