Breadth-First Seach (BFS)

Overview

Graph traversal is a search technique used to visit and explore all the nodes of a graph systematically. The primary goal of graph traversal is to uncover and examine the structure and connections of the graph. There are two common strategies for graph traversal:

• Breadth-First Seach (BFS)
• Depth-First Search (DFS)

The Breadth-First Search (BFS) algorithm explores a graph layer by layer and follows these steps:

1. Create a queue (first in, first out) to keep track of visited nodes.
2. Start from a selected node, enqueue it into the queue, and mark it as visited.
3. Dequeue a node from the front of the queue, enqueue all its unvisited neighbors into the queue and mark them as visited.
4. Repeat step 3 until the queue is empty.

Below is an example of traversing the graph using the BFS approach, starting from node A and assuming to visit neighbors in alphabetical order (A~Z):

Considerations

• Only nodes that are in the same connected component as the start node can be traversed. Nodes in different connect components will not be included in the traversal results.

Syntax

• Command: algo(traverse)
• Parameters:

Examples

File Writeback

UQL
algo(traverse).params({
  ids: ['A'],
  direction: 'out',
  traverse_type: 'bfs'
}).write({
  file: {
      filename: 'result'
  }
})

Results: File result

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