Séance 4 — Parcours & distances (BFS / DFS)¶

Objectifs pédagogiques¶

• Comprendre les notions de chemin, distance et ** composantes connexes**.
• Distinguer BFS (parcours en largeur) et DFS (parcours en profondeur).
• Utiliser networkx pour calculer des plus courts chemins dans un graphe non pondéré.
• Relier les distances à des interprétations sociologiques (proximité, relais, "six degrés").

Rappels¶

• Dans un graphe non pondéré, un plus court chemin est le chemin avec le moins d'arêtes.
• BFS explore par couches (distance croissante) et permet de trouver un plus court chemin.
• DFS explore en profondeur (par branches) ; utile pour détecter des cycles/composantes mais ne garantit pas un plus court chemin.

In [ ]:

# %pip install networkx matplotlib

import networkx as nx
import matplotlib.pyplot as plt
from collections import deque

# %pip install networkx matplotlib import networkx as nx import matplotlib.pyplot as plt from collections import deque

1) Graphe de départ : petit réseau social¶

In [ ]:

# Vous pouvez modifier/étendre ce graphe
G = nx.Graph()
G.add_edges_from([
    ("Alice","Bob"),
    ("Bob","Claire"),
    ("Claire","Emma"),
    ("Alice","David"),
    ("David","Emma"),
    ("Emma","Fanny"),
    ("Bob","Gaston"),
])

# Visualisation simple
plt.figure()
nx.draw(G, with_labels=True)
plt.show()

print("Nœuds :", list(G.nodes()))
print("Arêtes:", list(G.edges()))
print("Composantes connexes:", nx.number_connected_components(G))

# Vous pouvez modifier/étendre ce graphe G = nx.Graph() G.add_edges_from([ ("Alice","Bob"), ("Bob","Claire"), ("Claire","Emma"), ("Alice","David"), ("David","Emma"), ("Emma","Fanny"), ("Bob","Gaston"), ]) # Visualisation simple plt.figure() nx.draw(G, with_labels=True) plt.show() print("Nœuds :", list(G.nodes())) print("Arêtes:", list(G.edges())) print("Composantes connexes:", nx.number_connected_components(G))

Question : Y a-t-il un unique groupe connecté, ou plusieurs ? Impact sociologique : des individus isolés auront des distances infinies vers le reste.

2) Plus courts chemins et distances avec NetworkX¶

In [ ]:

source, cible = "Alice", "Fanny"
chemin = nx.shortest_path(G, source=source, target=cible)  # plus court chemin (non pondéré)
dist = nx.shortest_path_length(G, source=source, target=cible)
print(f"Plus court chemin de {source} à {cible} :", chemin)
print(f"Distance (nombre d'arêtes) :", dist)

source, cible = "Alice", "Fanny" chemin = nx.shortest_path(G, source=source, target=cible) # plus court chemin (non pondéré) dist = nx.shortest_path_length(G, source=source, target=cible) print(f"Plus court chemin de {source} à {cible} :", chemin) print(f"Distance (nombre d'arêtes) :", dist)

Exercice 2.1 : testez 3 autres paires (par ex. ('Gaston','Fanny'), ('Alice','Claire'), ('David','Bob')). Exercice 2.2 : si vous supprimez l'arête ('David','Emma'), que devient la distance Alice→Fanny ?

3) Implémenter un BFS pédagogique (pour comprendre l'ordre d'exploration)¶

In [ ]:

def bfs_layers(graph, start):
    """Retourne l'ordre de visite et les couches de distance (dict: noeud -> distance)
    BFS avec file d'attente (deque).
    """
    visited = set([start])
    dist = {start: 0}
    order = []
    q = deque([start])

    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.neighbors(u):
            if v not in visited:
                visited.add(v)
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

order, dist = bfs_layers(G, "Alice")
print("Ordre BFS depuis Alice:", order)
print("Distances depuis Alice:", dist)

def bfs_layers(graph, start): """Retourne l'ordre de visite et les couches de distance (dict: noeud -> distance) BFS avec file d'attente (deque). """ visited = set([start]) dist = {start: 0} order = [] q = deque([start]) while q: u = q.popleft() order.append(u) for v in graph.neighbors(u): if v not in visited: visited.add(v) dist[v] = dist[u] + 1 q.append(v) return order, dist order, dist = bfs_layers(G, "Alice") print("Ordre BFS depuis Alice:", order) print("Distances depuis Alice:", dist)

Exercice 3.1 : Comparez les distances renvoyées par bfs_layers et nx.shortest_path_length pour 3 nœuds. Exercice 3.2 : Quel nœud est le plus proche (distance minimale) d'Alice ? Le plus lointain ?

4) Implémenter un DFS (ordre d'exploration par branches)¶

In [ ]:

def dfs_order(graph, start, visited=None, order=None):
    if visited is None: visited = set()
    if order is None: order = []
    visited.add(start)
    order.append(start)
    for v in graph.neighbors(start):
        if v not in visited:
            dfs_order(graph, v, visited, order)
    return order

print("Ordre DFS depuis Alice:", dfs_order(G, "Alice"))

def dfs_order(graph, start, visited=None, order=None): if visited is None: visited = set() if order is None: order = [] visited.add(start) order.append(start) for v in graph.neighbors(start): if v not in visited: dfs_order(graph, v, visited, order) return order print("Ordre DFS depuis Alice:", dfs_order(G, "Alice"))

Exercice 4.1 : Pourquoi l'ordre DFS diffère-t-il souvent de l'ordre BFS ? Exercice 4.2 : DFS trouve-t-il un plus court chemin ? Expliquez avec un contre-exemple si possible.

5) Distances globales : diamètre & distance moyenne (si connexe)¶

In [ ]:

if nx.is_connected(G):
    # Diamètre = plus longue distance entre deux nœuds
    d = nx.diameter(G)
    # Distance moyenne (longueur moyenne des plus courts chemins)
    apl = nx.average_shortest_path_length(G)
    print("Diamètre:", d)
    print("Distance moyenne:", apl)
else:
    print("Le graphe n'est pas connexe : diamètre et distance moyenne ne sont pas définis globalement.")

if nx.is_connected(G): # Diamètre = plus longue distance entre deux nœuds d = nx.diameter(G) # Distance moyenne (longueur moyenne des plus courts chemins) apl = nx.average_shortest_path_length(G) print("Diamètre:", d) print("Distance moyenne:", apl) else: print("Le graphe n'est pas connexe : diamètre et distance moyenne ne sont pas définis globalement.")

Exercice 5.1 : Ajoutez/supprimez une arête et observez l'effet sur la distance moyenne. Interprétez sociologiquement (ex. apparition d'un pont qui réduit les distances).

6) Étude guidée : "six degrés de séparation" (mini-expérience)¶

In [ ]:

# Construisons un graphe en anneau + quelques liens longue portée pour réduire drastiquement les distances
H = nx.cycle_graph(12)  # 12 individus en cercle (0..11)
H = nx.relabel_nodes(H, {i: f"P{i}" for i in range(12)})
H.add_edge("P0","P6")   # raccourci longue portée
H.add_edge("P3","P9")   # autre raccourci

plt.figure()
nx.draw(H, with_labels=True)
plt.show()

print("Connexe:", nx.is_connected(H))
print("Distance moyenne:", nx.average_shortest_path_length(H))

# Construisons un graphe en anneau + quelques liens longue portée pour réduire drastiquement les distances H = nx.cycle_graph(12) # 12 individus en cercle (0..11) H = nx.relabel_nodes(H, {i: f"P{i}" for i in range(12)}) H.add_edge("P0","P6") # raccourci longue portée H.add_edge("P3","P9") # autre raccourci plt.figure() nx.draw(H, with_labels=True) plt.show() print("Connexe:", nx.is_connected(H)) print("Distance moyenne:", nx.average_shortest_path_length(H))

Questions

1. Que se passe-t-il si on retire les liens longue portée ?
2. Pourquoi quelques liens inter-groupes peuvent-ils réduire fortement les distances ?
3. Donnez une interprétation en termes de diffusion d'une rumeur/idée.

7) Synthèse écrite¶

• Comparez BFS et DFS sur votre graphe.
• Donnez 2 exemples de distances pertinentes en sociologie (ex. accès à l'information, recrutement).
• Proposez une hypothèse : l'ajout d'un lien entre deux groupes réduira X ; comment le tester ?