Publié · en amélioration
Algorithm
Le parcours de graphe visite tous les sommets accessibles par BFS ou DFS : la base des plus courts chemins non pondérés, composantes, cycles et tri topologique.
Le parcours de graphe consiste à visiter, une seule fois chacun, tous les sommets accessibles depuis un sommet de départ en suivant les arêtes. Les deux stratégies fondamentales sont le parcours en largeur (BFS), qui utilise une file pour progresser couche par couche, et le parcours en profondeur (DFS), qui utilise une pile ou la récursivité pour suivre une branche jusqu'au bout avant de revenir en arrière. On stocke généralement un graphe sous forme de listes d'adjacence ou de matrice d'adjacence, et une grille 2D comme un labyrinthe devient un graphe dès que chaque case est vue comme un sommet.
Les réseaux routiers, les réseaux sociaux, les dépendances entre tâches et les liens web sont des graphes. Le BFS trouve les plus courts chemins lorsque toutes les arêtes ont le même coût, tandis que le DFS sert de base aux composantes connexes, à la détection de cycles et au tri topologique. Les outils de build qui ordonnent leurs tâches, les ramasse-miettes qui déterminent ce qui reste accessible et l'outil de remplissage d'un éditeur d'images reposent tous sur un parcours, et c'est l'un des sujets les plus fréquents en entretien technique.
Commencez par dessiner un petit graphe et suivre à la main l'évolution de la file du BFS et de la pile d'appels du DFS. Implémentez ensuite les deux vous-même, en faisant attention au moment où les sommets sont marqués comme visités et à la façon d'enregistrer distances et parents. Passez enfin aux plus courts chemins dans une grille, au comptage des composantes connexes et au tri topologique avec l'algorithme de Kahn.
Les listes d'adjacence occupent O(V + E) et conviennent aux graphes creux ; la matrice teste une arête en O(1) mais occupe O(V^2).
Une file visite d'abord les sommets les plus proches : dans un graphe non pondéré, la première distance trouvée est la plus courte.
La récursivité ou une pile descend en profondeur puis remonte ; c'est la base des composantes, des cycles et du backtracking.
Dans un graphe orienté acyclique, l'algorithme de Kahn ou l'ordre de fin du DFS inversé donne un ordre qui respecte les dépendances.
Le programme construit un graphe non orienté de six sommets sous forme de listes d'adjacence dans un dictionnaire, puis affiche le plus petit nombre d'arêtes de A vers chaque sommet grâce à un BFS fondé sur deque, et l'ordre de visite d'un DFS récursif. Les deux fonctions mémorisent les sommets visités pour n'en traiter aucun deux fois.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySix chapitres pour aller de l'installation aux notions essentielles de Parcours de graphe.
Posez vos questions, partagez votre expérience et échangez vos avis sur Parcours de graphe.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.