10.1 Définition du tri topologique
Le tri topologique est un ordre linéaire des sommets d'un graphe orienté acyclique (DAG) tel que pour chaque arête (u, v), le sommet u précède le sommet v. Cet ordonnancement est possible uniquement pour les DAG et ne peut pas être effectué sur des graphes comportant des cycles.
Comment trouves-tu la définition ? Si tu l'as comprise du premier coup, tu as probablement pas mal d'expérience avec les algorithmes.
En des termes simples, ça donne ça : tu as une liste de tâches (les sommets du graphe) et une liste de dépendances entre elles (les flèches dans le graphe). Arrange les tâches (sommets) de sorte que toutes les tâches dont dépend « tâche A » soient effectuées avant elle. Tout devient clair, au lieu de « ordre linéaire des sommets d'un graphe orienté acyclique »...
Le tri topologique est un algorithme super important en pratique, c'est pour ça qu'il a son propre nom, et pas juste celui de son auteur. Voyons où il est nécessaire :
Applications :
1. Planification de tâches (Task Scheduling) :
Déterminer l'ordre d'exécution des tâches dépendantes de manière à ce que chaque tâche soit exécutée après toutes ses dépendances.
Exemple :
Planification de projets dans un système de gestion de projet.
2. Compilation de code :
Déterminer l'ordre de compilation des modules ou fichiers source qui dépendent les uns des autres.
Exemple :
Optimisation de la construction de logiciels dans les systèmes de build (par exemple, Makefile).
3. Résolution des dépendances dans les gestionnaires de paquets :
Ordonner les paquets de manière à ce que toutes les dépendances soient installées avant l'installation du paquet lui-même.
Exemple :
Simplification du processus d’installation de logiciels dans les gestionnaires de paquets (par exemple, npm, pip, apt).
4. Optimisation des itinéraires :
Déterminer l'ordre de visite des points ou d'exécution des actions en tenant compte des dépendances entre eux.
Exemple :
Logistique et planification des itinéraires de livraison de marchandises.
Complexité temporelle et spatiale du tri topologique :
Complexité temporelle :
Les deux principaux algorithmes de tri topologique (DFS et algorithme de Kahn) ont une complexité temporelle de O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes dans le graphe.
Complexité spatiale :
La complexité spatiale des deux algorithmes est de O(V + E), car cela nécessite de stocker le graphe ainsi que des tableaux pour suivre les sommets visités et leurs prédécesseurs.
10.2 Implémentation via recherche en profondeur (DFS)
On peut effectuer un tri topologique de différentes manières, dont l'une s'appuie sur la recherche en profondeur — DFS. L'algorithme DFS pour le tri topologique utilise une pile pour suivre les nœuds complétés.
Exemple d'implémentation :
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # Résultat dans l'ordre inverse
# Exemple d'utilisation :
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Tri topologique :", result)
Sortie :
Tri topologique : ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Implémentation : algorithme de Kahn
Une autre approche est appelée algorithme de Kahn (Kahn's Algorithm). L'algorithme de Kahn pour le tri topologique utilise le concept de degrés entrants des sommets.
Exemple d'implémentation :
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("Le graphe contient un cycle")
# Exemple d'utilisation :
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Tri topologique :", result)
Sortie :
Tri topologique : ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION