Le DOM que l'on manipule tous les jours est un arbre n-aire (n-ary tree) constitué de nœuds JavaScript.
Quand on invoque querySelector(), le navigateur traverse l'arbre du DOM pour trouver l'élément qu'on lui a demandé en suivant un algorithme de parcours en profondeur. C'est un algorithme de parcours de graphe.
Et les arbres ne sont qu'un sous-ensemble des graphes.
La prochaine étape de mon odyssée en science du computer sera donc les graphes qui servent à traduire pas mal de problèmes dans plein de domaines différents dont l'intelligence artificielle.
Les graphes
Un graphe est une collection de nœuds (ou sommets, ou vertices en anglais) dont certains sont reliés entre eux par des branches (ou liens, ou arêtes, ou arcs, ou edges en anglais).
Les liens entre les nœuds peuvent être orientés ou non orientés. Dans ce dernier cas les liens sont symétriques.
Un graphe peut être implémenté via une liste d'adjacence ou via une matrice d'adjacence.
Un graphe peut contenir des boucles (cycles). Il est dit acyclique s'il n'en possède pas.
Les algorithmes de parcours de graphe les plus étudiés sont le parcours en profondeur et le parcours en largeur qui ont certains cas d'usage différents.
Pour compléter mes notes, voici des exemples d'implémentation de ces algorithmes dont le code est quasi décalqué de celui de Edd Mann que j'ai trouvé facile à lire pour une première approche.
Représentation d'un graphe
On se sert d'une liste d'adjacence implémentée grâce à un dictionnaire (source de l'exemple) :
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C'],
}
Cette structure représente un graphe constitué de 6 nœuds (A-F) et de 8 liens :
A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C
Le graphe obtenu est orienté et peut se représenter de la manière suivante :
Parcours en profondeur (DFS)
Pour le parcours en profondeur (DFS pour Depth-First Search), on commence avec un nœud donné et on explore chaque branche complètement avant de passer à la suivante. Autrement dit, on commence d'abord par aller le plus profond possible.
Cet algorithme s'écrit naturellement de manière récursive et permet de trouver tous les nœuds auquel un nœud est connecté :
def recursive_dfs(graph, node, visited=None):
if visited is None:
visited = []
if node not in visited:
visited.append(node)
unvisited = [n for n in graph[node] if n not in visited]
for node in unvisited:
recursive_dfs(graph, node, visited)
return visited
Pour voir la chaîne des nœuds connectés depuis un nœud donné :
>>> recursive_dfs(graph, "E")
['E', 'F', 'C', 'D']
>>> recursive_dfs(graph, "F")
['F', 'C', 'D']
On peut aussi écrire le parcours en profondeur de façon itérative grâce à une pile (stack) :
from collections import deque
def iterative_dfs(graph, node):
visited = []
stack = deque()
stack.append(node)
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
unvisited = [n for n in graph[node] if n not in visited]
stack.extend(unvisited)
return visited
Une de ses utilités est de pouvoir déterminer s'il existe des chemins d'un nœud à un autre :
from collections import deque
def find_paths_dfs(graph, start, end):
stack = deque()
stack.append((start, [start]))
while stack:
(node, path) = stack.pop()
adjacent_nodes = [n for n in graph[node] if n not in path]
for adjacent_node in adjacent_nodes:
if adjacent_node == end:
yield path + [adjacent_node]
else:
stack.append((adjacent_node, path + [adjacent_node]))
Parcours en largeur (BFS)
Pour le parcours en largeur (BFS pour Breadth-First Search), on commence avec un nœud donné et on explore chacun de ses voisins avant d'explorer leurs enfants. Autrement dit, on commence d'abord par aller sur la plus grande largeur possible.
Son implémentation repose sur une file (queue) dont le principe du premier entré, premier sorti permet de s'assurer que les nœuds découverts d'abord seront explorés en premier :
from collections import deque
def iterative_bfs(graph, start):
visited = []
queue = deque()
queue.append(start)
while queue:
node = queue.popleft()
if node not in visited:
visited.append(node)
unvisited = [n for n in graph[node] if n not in visited]
queue.extend(unvisited)
return visited
Il permet aussi de déterminer s'il existe des chemins d'un nœud à un autre :
from collections import deque
def find_paths_bfs(graph, start, end):
queue = deque()
queue.append((start, [start]))
while queue:
node, path = queue.popleft()
adjacent_nodes = [n for n in graph[node] if n not in path]
for adjacent_node in adjacent_nodes:
if adjacent_node == end:
yield path + [adjacent_node]
else:
queue.append((adjacent_node, path + [adjacent_node]))
Joint