Représentations de graphes: Stocker les sommets et arêtes d'un graphe sous forme de matrice d'adjacence ou de liste d'adjacence.
Piles et files: Deux ordonnancements à accès restreint : dernier entré, premier sorti et premier entré, premier sorti.
Mène à
Tri topologique: Ordonner les sommets d'un graphe orienté acyclique pour que chaque arête pointe vers l'avant.
Algorithme de Dijkstra: Trouver le chemin le moins coûteux d'un sommet vers tous les autres quand aucun poids d'arête n'est négatif.
Algorithme de Bellman-Ford: Trouver les plus courts chemins tout en fonctionnant encore lorsque certains poids d'arêtes sont négatifs, au prix de la vitesse.
Notions liées
Tri topologique: Ordonner les sommets d'un graphe orienté acyclique pour que chaque arête pointe vers l'avant.
Retour sur trace (backtracking): Essayer un choix, récurer, puis l'annuler s'il ne mène nulle part, pour explorer toutes les possibilités.