Vidéo: Cours 71 refait : structures arborescentes 2025
Les graphes sont une forme de structure de données commune utilisée dans les algorithmes. Vous voyez des graphiques utilisés dans des endroits comme des cartes pour GPS et toutes sortes d'autres endroits où l'approche descendante d'une structure arborescente ne fonctionnera pas.
Un graphe est une sorte d'extension d'arbre. Comme pour les arbres, vous avez des nœuds qui se connectent les uns aux autres pour créer des relations. Cependant, contrairement aux arbres binaires, un graphe peut avoir plus d'une ou deux connexions. En fait, les nœuds graphiques ont souvent une multitude de connexions. Pour garder les choses simples, cependant, considérez le graphique montré.
Dans ce cas, le graphique crée un anneau où A se connecte à la fois à B et à F. Cependant, cela n'a pas à être le cas. A peut être un nœud déconnecté ou peut également se connecter à C. Un graphique montre la connectivité entre les nœuds d'une manière utile pour définir des relations complexes.
Les graphiques ajoutent également quelques nouveaux rebondissements auxquels vous n'avez peut-être jamais pensé auparavant. Par exemple, un graphique peut inclure le concept de directionnalité. Contrairement à un arbre, qui a des relations parents / enfants, un noeud graphique peut se connecter à n'importe quel autre noeud avec une direction spécifique en tête. Pensez aux rues dans une ville. La plupart des rues sont bidirectionnelles, mais certaines sont des rues à sens unique qui permettent le mouvement dans une seule direction.
La présentation d'une connexion graphique peut ne pas refléter réellement les réalités du graphique. Un graphique peut désigner un poids à une connexion particulière. Le poids peut définir la distance entre deux points, définir le temps nécessaire pour parcourir la route ou fournir d'autres types d'informations.
