Arbres et graphes

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

Représentation	Espace	Test d'arête	Parcours voisins
Matrice d'adjacence	$O(n^2)$	$O(1)$	$O(n)$
Liste d'adjacence	$O(n + m)$	$O(\deg)$	$O(\deg)$

# 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).