Arbres et graphes

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Arbres - définition

Une image d'un arbre avec des nœuds.

  • Structures basées sur des nœuds
  • Chaque nœud peut avoir liens vers plus d’un nœud.
Structures de données et algorithmes en Python

Arbres - terminologie

Une image d’un arbre avec des nœuds. Le nœud racine est coloré en jaune.

Structures de données et algorithmes en Python

Arbres - terminologie

Une image d’un arbre avec des nœuds. Le nœud racine est coloré en jaune. Un nœud parent est coloré en orange.

Structures de données et algorithmes en Python

Arbres - terminologie

Une image d’un arbre avec des nœuds. Le nœud racine est coloré en jaune. Un nœud parent est coloré en orange et ses enfants sont colorés en vert.

Structures de données et algorithmes en Python

Arbres - terminologie

Une image d’un arbre avec des nœuds.

Structures de données et algorithmes en Python

Arbres - terminologie

Une image d’un arbre avec des nœuds à ses différents niveaux.

Structures de données et algorithmes en Python

Arbres - arbre binaire

Représentation graphique d’un arbre binaire.

  • Chaque nœud a :
    • zéro enfant
    • un enfant
    • deux enfants
Structures de données et algorithmes en Python

Arbres - Implémentation d’un arbre binaire

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

Une image d'un arbre avec des nœuds.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Structures de données et algorithmes en Python

Les arbres - usages réels

  • Stockage des relations hiérarchiques
    • Système de fichiers d’un ordinateur
    • Structure d’un document HTML

  • Échecs : coups possibles du rival

  • Algorithmes de recherche et tri

Structures de données et algorithmes en Python

Graphes

Une image d’un graphe avec des nœuds.

  • Ensemble de :
    • nœuds/sommets
    • liens/arêtes
  • Les arbres sont un type de graphe
Structures de données et algorithmes en Python

Graphes - types

  • Graphes orientés :
    • Direction spécifique

Image d’un graphe orienté.

Structures de données et algorithmes en Python

Graphes - types

  • Graphes non orientés :
    • Arêtes n’ont pas de direction
    • La relation est mutuelle

Image d'un graphe non orienté.

Structures de données et algorithmes en Python

Graphes - types

  • Graphes pondérés :
    • valeurs numériques associées aux arêtes
    • peut être orienté ou non orienté

Une image d’un graphe non orienté avec les noms de certaines villes et la distance entre elles.

Structures de données et algorithmes en Python

Graphes vs arbres

Arbres

  • Ne peut pas avoir de cycles
  • Tous nœuds doivent être connectés

Une image d'un arbre avec des nœuds.

Graphes

  • Peut avoir des cycles
  • Peut y avoir nœuds non connectés

Une image d’un graphique avec des nœuds.

Structures de données et algorithmes en Python

Graphes vs arbres

Arbres

  • Ne peut pas avoir de cycles
  • Tous les nœuds doivent être connectés

Une image d’un arbre avec des nœuds.

Graphes

  • Peut avoir des cycles
  • Peut y avoir nœuds non connectés

Une image d’un graphique avec des nœuds. Il y a un nœud qui n’est pas connecté au reste.

Structures de données et algorithmes en Python

Graphes - cas d’usage réels

  • Relations utilisateur sur réseaux sociaux
    • amitié
    • suit
    • aime
    • etc.
  • Lieux et distances
    • optimiser itinéraires
  • Bases de données graphes
  • Algorithmes de recherche et tri
Structures de données et algorithmes en Python

Graphes - Implémentation

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Image d’un graphe orienté.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...