Le parcours en largeur
Le parcours en largeur a pour philosophie d’aller explorer les nœuds du graphe par éloignement croissant (au sens du nombre d’arêtes minimum d’un chemin les reliant) avec un nœud de départ u.
Il permet de trouver l’ensemble des nœuds atteignables à partir de u, c’est-à-dire l’ensemble des nœuds v pour lesquels il existe un chemin reliant u à v. De plus, il permet de trouver pour tout tel v le plus court chemin entre u et v.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# The arguments are a graph to explore and a source node. # It prints to stdout the list of visited nodes, along with a shortest path to them def breadthFirstSearch (graph, sourceNode) : # First we initialize the queue # We insert the sourceNode and a shortest path to it # We also mark the source node as visited queue = [(sourceNode, [sourceNode])] visited = [sourceNode] # We then explore the graph while queue : # We extract the oldest node from the queue (currentNode, path) = queue[0] queue = queue[1:] print(currentNode, "path =", repr(path)) # We add all neighbors of currentNode not already visited for neighbor in graph[currentNode] : if neighbor not in visited : queue.append((neighbor, path + [neighbor])) visited.append(neighbor) ################################################################### # Test graph graph = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]] breadthFirstSearch(graph, 0) |
Dans cet exemple, le graphe utilisé est le suivant, où le nœud source est 0 (représenté sous forme d’un tableau de listes) :
Retrouver le chemin à partir du parcours
Pour retrouver le chemin ayant mené du nœud initial au nœud visité, on peut créer une table de routage, qui retiendra pour tout nœud lequel l’aura ajouté à la file. Le code précédent devient :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
# The arguments are a graph to explore and a source node. # It prints to stdout the list of visited nodes, along with a shortest path to them def breadthFirstSearch (graph, sourceNode) : # First we initialize the queue # We insert the sourceNode and a shortest path to it # We also mark the source node as visited queue = [(sourceNode, [sourceNode])] visited = [sourceNode] routes = [None for i in range(len(graph))] # <-- new (we keep track of the predecessors) # We then explore the graph while queue : # We extract the oldest node from the queue (currentNode, path) = queue[0] queue = queue[1:] print(currentNode, "path =", repr(path)) # We add all neighbors of currentNode not already visited for neighbor in graph[currentNode] : if neighbor not in visited : queue.append((neighbor, path + [neighbor])) visited.append(neighbor) routes[neighbor] = currentNode # <-- new (the neighbor is visited from the current node) # We show the routes print(repr(routes)) # <-- new (we print the resulting routes) ################################################################### # Test graph graph = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]] breadthFirstSearch(graph, 0) |
Pour cet exemple, la table de routage affichée est [None, 0, 0, 5, 5, 0].
Une fois la table de routage trouvée, il est facile de retrouver les chemins amenant du nœud initial (ici, 0) aux autres. Si on cherche le chemin de 0 à 4 par exemple, il suffit de regarder le prédécesseur de 4, situé en routes[4]. Ce prédécesseur est 5 d’après la table de routage. On regarde donc routes[5], et on trouve 0.
Le chemin trouvé par l’algorithme pour aller de 0 à 4 est donc 0 – 5 – 4.
Propriétés de l’algorithme
Terminaison
L’algorithme ne visite qu’une fois chaque nœud atteignable, et donc termine.
Correction
L’algorithme du parcours en largeur donne le plus court chemin d’un nœud u à tous les nœuds atteignables depuis u dans le graphe.
Nous allons montrer que :
- Les nœuds sont visités par distance croissante au nœud u
- Les chemins obtenus sont de longueur minimale
- Tous les nœuds atteignables sont visités
Les nœuds sont visités par distance croissante au nœud u
Supposons par l’absurde le premier moment où un nœud v est ajouté à la file et est strictement plus proche de u qu’un nœud w qui y était déjà. Notons p le nœud voisin de v qui le rajoute à la file. Deux cas alors :
- Soit w est plus proche de u que p et nous arrivons à une contradiction (lorsque w a été ajouté, il y avait un nœud dans la file plus loin, et ce n’est donc pas le premier moment où cela se produit).
- Soit la distance de u à p est la même que celle de u à w. On en conclut que v est plus proche de u que p. Notons k un prédecesseur de v dans un chemin le plus court de u à v. On en déduit que k n’a pas été visité sinon v aurait déjà été ajouté à la file. En remontant ainsi par récurrence, on en déduit qu’un voisin direct de u n’a pas été ajouté à la file, donc que p=u, donc que v ne peut pas être plus proche de u que p.
Les chemins obtenus sont de longueur minimale
Ceci se prouve par récurrence : nous allons montrer qu’à tout moment, les chemins dans la file sont des chemins minimaux. C’est clairement vrai au départ pour le nœud initial u. Ensuite la propriété 1. nous assure qu’ajouter un nœud dans la file se fait forcément par un voisin étant un prédecesseur sur un chemin minimal depuis u.
Tous les nœuds atteignables sont visités
Notons par l’absurde v un nœud atteignable mais non visité par l’algorithme à distance minimale de u. De façon analogue, on va considérer un chemin le plus court de u à v. Notons k le prédecesseur de v sur ce chemin. On en déduit que k n’a pas été visité (sinon il aurait ajouté v à la file). Donc k est atteignable et non visité ; il est de plus plus proche de u que v. Contradiction.
Complexité
L’algorithme ne visite qu’une fois chaque sommet, et à chaque fois consulte la liste des voisins. on en déduit qu’il est en O(m) où m est le nombre d’arêtes dans le graphe.