Vue d’ensemble

La traversée de graph est une technique de recherche utilisée pour visiter et explorer systématiquement tous les nodes d'un graph. L'objectif principal de la traversée de graph est de découvrir et d'examiner la structure et les connexions du graph. Il existe deux stratégies courantes pour la traversée de graphs :

• Recherche en largeur (BFS)
• Recherche en profondeur (DFS)

L'algorithme de Recherche en Profondeur (DFS) fonctionne selon le principe du retour en arrière et suit les étapes suivantes :

1. Créez une pile (dernier entré, premier sorti) pour garder une trace des nodes visités.
2. Commencez à partir d'un node sélectionné, poussez-le dans la pile et marquez-le comme visité.
3. Poussez tout voisin non visité du node au sommet de la pile dans la pile, et marquez-le comme visité. S'il y a plusieurs voisins non visités, choisissez-en un arbitrairement ou selon un certain ordre.
4. Répétez l'étape 3 jusqu'à ce qu'il n'y ait plus de voisins non visités à pousser dans la pile.
5. Lorsqu'il n'y a plus de nouveaux nodes à visiter, revenez au node précédent (celui à partir duquel le node actuel a été exploré) en retirant le node en haut de la pile.
6. Répétez les étapes 3, 4 et 5 jusqu'à ce que la pile soit vide.

Voici un exemple de traversée du graph à l'aide de l'approche DFS, en commençant par le node A et en supposant de visiter les voisins dans l'ordre alphabétique (A~Z) :

Considérations

• Seuls les nodes qui se trouvent dans le même composant connecté que le node de départ peuvent être parcourus. Les nodes dans différents composants connectés ne seront pas inclus dans les résultats de la traversée.

Syntaxe

• Commande : algo(traverse)
• Paramètres :

Exemples

File Writeback

algo(traverse).params({
  ids: ['B'],
  direction: 'in',
  traverse_type: 'dfs'
}).write({
  file: {
      filename: 'result'
  }
})

Résultats : Fichier result

F,C
E,F
C,A
B,B
A,B