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 !