Breadth-First Search (BFS)

Overview

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

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

The BFS algorithm explores a graph level by level and proceeds as follows:

1. Create a queue (first in, first out) to keep track of visited nodes.
2. Start from a selected node, enqueue it and mark 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.

The following example demonstrates BFS traversal starting from node A, assuming neighbors are visited in alphabetical order (A–Z):

Considerations

• Only nodes within the same connected component as the start node will be traversed. Nodes in other connected components are excluded from the traversal results.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (A)-[:default]->(B), (A)-[:default]->(D),
       (B)-[:default]->(E), (C)-[:default]->(A),
       (E)-[:default]->(F), (F)-[:default]->(C),
       (G)-[:default]->(D)

Parameters

Run Mode

Returns:

GQL
CALL algo.bfs({
  startNode: "A"
}) YIELD nodeId, depth, parent

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.bfs.stream({
  startNode: "A",
  maxDepth: 2
}) YIELD nodeId, depth
RETURN nodeId, depth

Result:

Stats Mode

Returns:

GQL
CALL algo.bfs.stats({
  startNode: "A"
}) YIELD nodeCount, maxDepth

Result: