data-structures
Traversées de graphiques

Introduction

Depth First Search

Depth First Traversal (ou Search) pour un graphique est similaire à Depth First Traversal d'un arbre. Le seul problème ici est que, contrairement aux arbres, les graphiques peuvent contenir des cycles, nous pouvons donc revenir au même nœud. Pour éviter de traiter un nœud plusieurs fois, nous utilisons un tableau booléen visité.

L'algorithme ci-dessous présente les étapes pour la traversée de graphe en utilisant DFS:

Algorithme DFS (v);

Entrée : Un sommet v dans un graphique

Sortie : un étiquetage des arêtes comme arêtes de “découverte” et “backedges”

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

Largeur Première Recherche

Algorithme BFS (G)

Graphe d'entrée G

Etiquetage en sortie des arêtes et partition des sommets de G

    for all u ∈ G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ∈ G.edges()
    setLabel
    (e, UNEXPLORED)
    for all v ∈ G.vertices()
        if getLabel(v) = UNEXPLORED
            BFS(G, v)