Arbres et graphes

En clair. Parcours, applications

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Arbres et graphes », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

Arbres et graphes

Définitions

Un graphe $G = (S, A)$ est constitué d'un ensemble de sommets $S$ et d'un ensemble d'arêtes $A \subseteq S \times S$. Il est :

• orienté si les arêtes ont un sens (arcs), non orienté sinon ;
• pondéré si chaque arête porte un poids (distance, coût, capacité) ;
• connexe s'il existe un chemin entre toute paire de sommets.

Un arbre est un graphe non orienté connexe sans cycle. Pour un arbre à $n$ sommets, il y a exactement $n-1$ arêtes. Un arbre enraciné distingue un sommet (la racine) ; on parle alors de père, fils, frères, feuilles et nœuds internes.

Représentations en mémoire

# Liste d'adjacence (graphe orienté pondéré)
graphe = {
    'A': [('B', 5), ('C', 2)],
    'B': [('D', 3)],
    'C': [('B', 1), ('D', 6)],
    'D': []
}

Parcours

Parcours en profondeur (DFS) — utilise une pile (récursive ou explicite) :

def dfs(g, s, vus=None):
    if vus is None: vus = set()
    vus.add(s)
    for v, _ in g[s]:
        if v not in vus:
            dfs(g, v, vus)
    return vus

Parcours en largeur (BFS) — utilise une file ; donne le plus court chemin en nombre d'arêtes dans un graphe non pondéré.

from collections import deque
def bfs(g, depart):
    vus, file = {depart}, deque([depart])
    while file:
        s = file.popleft()
        for v, _ in g[s]:
            if v not in vus:
                vus.add(v); file.append(v)

Complexité des deux : $O(n + m)$.

Arbres binaires

Un arbre binaire : chaque nœud a au plus 2 fils. Trois parcours classiques :

• préfixe (racine, gauche, droite),
• infixe (gauche, racine, droite) — donne une suite triée pour un ABR,
• suffixe (gauche, droite, racine).

Un arbre binaire de recherche (ABR) vérifie : pour tout nœud $x$, les clés du sous-arbre gauche sont $< x$ et celles du sous-arbre droit sont $> x$. Recherche, insertion, suppression : $O(h)$ où $h$ est la hauteur ($O(\log n)$ si équilibré, $O(n)$ dans le pire cas).