Arbres et graphes

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Arbres - définition

Image d’un arbre avec des nœuds.

Structures de données à nœuds
Chaque nœud peut avoir des liens vers plus d’un nœud.

Arbres - terminologie

Image d’un arbre avec des nœuds. Le nœud racine est en jaune.

Arbres - terminologie

Image d’un arbre avec des nœuds. Le nœud racine est en jaune. Un nœud parent est en orange.

Arbres - terminologie

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

Arbres - terminologie

Image d’un arbre avec des nœuds.

Arbres - terminologie

Image d’un arbre avec des nœuds à différents niveaux.

Arbres - arbre binaire

Représentation graphique d’un arbre binaire.

Chaque nœud a :
- zéro enfant
- un enfant
- deux enfants

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

Image d’un arbre avec des nœuds.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

Arbres - usages réels

Stocker des relations hiérarchiques
- Système de fichiers d’un ordinateur
- Structure d’un document HTML
Échecs : coups possibles de l’adversaire
Algorithmes de recherche et de tri

Graphes

Image d’un graphe avec des nœuds.

Ensemble de :
- nœuds/sommets
- liens/arêtes
Les arbres sont un type de graphe

Graphes - types

Graphes orientés :
- direction spécifique

Image d’un graphe orienté.

Graphes - types

Graphes non orientés :
- Les arêtes n’ont pas de direction
- La relation est réciproque

Image d’un graphe non orienté.

Graphes - types

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

Image d’un graphe non orienté avec des noms de villes et les distances entre elles.

Graphes vs. arbres

Arbres

Pas de cycles
Tous les nœuds doivent être connectés

Image d’un arbre avec des nœuds.

Graphes

Peuvent avoir des cycles
Des nœuds peuvent être non connectés

Image d’un graphe avec des nœuds.

Graphes vs. arbres

Arbres

Pas de cycles
Tous les nœuds doivent être connectés

Image d’un arbre avec des nœuds.

Graphes

Peuvent avoir des cycles
Des nœuds peuvent être non connectés

Image d’un graphe avec des nœuds. Un nœud n’est pas connecté au reste.

Graphes - cas d’usage réels

Relations entre utilisateurs dans les réseaux sociaux
- amitié
- abonnements
- mentions J’aime
- etc.
Lieux et distances
- optimiser des itinéraires
Bases de données graphe
Algorithmes de recherche et de tri

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' : []
}

Passons à la pratique !

Structures de données et algorithmes en Python