Piles, files, liste chainées, arbres, graphes ...
Somme des feuilles, arbre complet, miroir d'un arbre
Dans ce TD, nous allons implémenter des arbres binaires en Python. On choisit de représenter l'arbre vide par la liste vide, et un arbre de racine étiquetée par e et fils fg et fd par la liste [e, fg, fd]
Un graphe G=(S,A) est dit connecté, si pour tout couple de sommets (u, v) il existe un chemin reliant u et v
L’idée est simple : pour vérifier l’existence d’un cycle dans un graphe, il suffit de déterminer s’il existe, pour un sommet v, un chemin qui part de v et y revient ; si un tel chemin existe, alors le graphe contient un cycle.
L'algorithme de Floyd-Warshall change de paradigme. Son objectif est de calculer simultanément les distances minimales pour tous les couples de sommets \((i,j)\). C'est un outil indispensable pour l'analyse de réseaux denses (où le nombre d'arêtes \(A\) est proche de \(S^2\)) et pour la détection de structures pathologiques comme les cycles de poids négatifs.
L'algorithme de Bellman-Ford est un algorithme de calcul des plus courts chemins depuis une source unique dans un graphe pondéré. Développé par Richard Bellman et Lester Ford dans les années 1950, il constitue une alternative plus robuste mais moins efficace que l'algorithme de Dijkstra.
L'algorithme a été conçu par Edsger W. Dijkstra en 1956 et publié en 1959. Dans sa lettre originale, il décrit sa découverte comme une solution "en 20 minutes" à un problème posé par un mathématicien non informaticien. La simplicité de sa formulation cache une profondeur conceptuelle qui en fait l'un des joyaux de l'algorithmique des graphes.
Le BFS explore un graphe par niveaux successifs, du plus proche au plus éloigné. Le DFS explore un graphe en s'enfonçant le plus loin possible le long d'un chemin avant de revenir en arrière (backtracking).
Ce cours présente les différentes manières de représenter un graphe en mémoire pour permettre son traitement algorithmique. Vous y apprendrez : la liste d'adjacence, la matrice d'adjacence et la matrice d'incidence
Comment supprimer un noeud de l'arbre binaire de recherche ?
Introduction à l'arbre binaire de recherche
Insertion et suppression d'un élément de l'arbre binaire