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 de traversée de graph :

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

L'algorithme de Recherche en largeur (BFS) explore un graph couche par couche et suit ces étapes :

1. Créer une file d'attente (premier entré, premier sorti) pour suivre les nodes visités.
2. Commencer à partir d'un node sélectionné, l'enfiler dans la file d'attente et le marquer comme visité.
3. Défiler un node depuis l'avant de la file d'attente, enfiler tous ses voisins non visités dans la file d'attente et les marquer comme visités.
4. Répéter l'étape 3 jusqu'à ce que la file d'attente soit vide.

Ci-dessous un exemple de traversée du graph en utilisant l'approche BFS, en commençant par le node A et en supposant visiter les voisins par ordre alphabétique (A~Z) :

Considerations

• Seuls les nodes qui sont dans le même composant connecté que le node de départ peuvent être traversés. 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: ['A'],
  direction: 'out',
  traverse_type: 'bfs'
}).write({
  file: {
      filename: 'result'
  }
})

Résultats : Fichier result

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