Introduction

Présentation générale

Les graphes et les arbres sont des structures de données non linéaires permettant de modéliser un grand nombre de problèmes différents (gestion de ressources, représentation de réseaux, etc.)

Suivant les problèmes qu'ils modélisent, de nombreux algorithmes et diverses implémentations ont également été développés.

Le but de cette partie est de présenter ces deux grandes structures de données, tout d'abord de façon abstraite, puis avec différentes implémentations. Différents algorithmes classiques sur ces structures sont également abordés.

Points abordés

1. Généralités sur les graphes :

   • introduction historique ;
   • classification des graphes (non orienté, orienté, valué) ;
   • vocabulaire : sommet, arête/arc, coût, adjacence, degré, voisin ;
   • chemin/cycle dans un graphe, connexité.

2. Représentation des graphes :

   • matrice et listes d'adjacence ;
   • implémentation.

3. Parcours de graphes :

   • parcours en largeur ;
   • parcours en profondeur ;
   • implémentation et applications.

4. Généralités sur les arbres :

   • notion d'arbres ;
   • définition récursive ;
   • vocabulaire de base : racine, feuille, noeud ;
   • généalogie : père, fils et frères ;
   • quelques mesures : profondeur, niveau et hauteur.

5. Algorithmes de Dijkstra, Prim et Kruskal :

   • problème du plus court chemin ;
   • arbre couvrant minimal.

6. Arbres binaires :

   • vocabulaire sur les arbres binaires : père, fils gauche, fils droit ;
   • parcours en largeur ;
   • parcours en profondeur avec traitement préfixé, infixé et postfixé ;
   • algorithmes et implémentations.

7. Arbres binaires de recherche (ABR) :

   • structure d'un ABR ;
   • affichage et recherche de clés ;
   • ajout de clés ;
   • algorithmes et implémentations.