> ## Documentation Index
> Fetch the complete documentation index at: https://new.docs.falkordb.com/llms.txt
> Use this file to discover all available pages before exploring further.

# BFS

> Breadth-First Search (BFS) explores a graph level by level, visiting all neighbors of a node before moving to the next depth.

## Overview

The Breadth-First Search (BFS) procedure allows you to perform a breadth-first traversal of a graph starting from a specific node.
BFS explores all the nodes at the present depth before moving on to nodes at the next depth level.
This is particularly useful for finding the shortest path between two nodes or exploring a graph layer by layer.

## Syntax

```cypher theme={null}
CALL algo.bfs(start_node, max_depth, relationship)
YIELD nodes, edges
```

## Arguments

| Name         | Type           | Description                                                                 | Default    |
| ------------ | -------------- | --------------------------------------------------------------------------- | ---------- |
| start\_node  | Node           | Starting node for the BFS traversal                                         | (Required) |
| max\_depth   | Integer        | Maximum depth to traverse                                                   | (Required) |
| relationship | String or null | The relationship type to traverse. If null, all relationship types are used | null       |

## Returns

| Name  | Type | Description                                  |
| ----- | ---- | -------------------------------------------- |
| nodes | List | List of visited nodes in breadth-first order |
| edges | List | List of edges traversed during the BFS       |

## Examples

### Social Network Friend Recommendations

This example demonstrates how to use BFS to find potential friend recommendations in a social network.
By exploring friends of friends, BFS uncovers second-degree connections—people you may know through mutual friends—which are often strong candidates for relevant and meaningful recommendations.

#### Create the Graph

```cypher theme={null}
CREATE 
  (alice:Person {name: 'Alice', age: 28, city: 'New York'}),
  (bob:Person {name: 'Bob', age: 32, city: 'Boston'}),
  (charlie:Person {name: 'Charlie', age: 35, city: 'Chicago'}),
  (david:Person {name: 'David', age: 29, city: 'Denver'}),
  (eve:Person {name: 'Eve', age: 31, city: 'San Francisco'}),
  (frank:Person {name: 'Frank', age: 27, city: 'Miami'}),

  (alice)-[:FRIEND]->(bob),
  (alice)-[:FRIEND]->(charlie),
  (bob)-[:FRIEND]->(david),
  (charlie)-[:FRIEND]->(eve),
  (david)-[:FRIEND]->(frank),
  (eve)-[:FRIEND]->(frank)
```

<img src="https://mintcdn.com/falkordb-core/4RKo-4HTPunDsB0h/images/graph_bfs.png?fit=max&auto=format&n=4RKo-4HTPunDsB0h&q=85&s=6f2dade91e15620494a78726d566ec4c" alt="Graph BFS" width="1640" height="870" data-path="images/graph_bfs.png" />

#### Find Friends of Friends (Potential Recommendations)

```cypher theme={null}
// Find Alice's friends-of-friends (potential recommendations)
MATCH (alice:Person {name: 'Alice'})
CALL algo.bfs(alice, 2, 'FRIEND')
YIELD nodes

// Process results to get only depth 2 connections (friends of friends)
WHERE size(nodes) >= 3
WITH alice, nodes[2] AS potential_friend
WHERE NOT (alice)-[:FRIEND]->(potential_friend)
RETURN potential_friend
```

In this social network example, the BFS algorithm helps find potential friend recommendations by identifying people who are connected to Alice's existing friends but not directly connected to Alice yet.

## Performance Considerations

* **Indexing:** Ensure properties used for finding your starting node are indexed for optimal performance
* **Maximum Depth:** Choose an appropriate max\_depth value based on your graph's connectivity; large depths in highly connected graphs can result in exponential growth of traversed nodes
* **Relationship Filtering:** When applicable, specify the relationship type to limit the traversal scope
* **Memory Management:** Be aware that the procedure stores visited nodes in memory to avoid cycles, which may require significant resources in large, densely connected graphs

## Error Handling

Common errors that may occur:

* **Null Starting Node:** If the start\_node parameter is null, the procedure will raise an error; ensure your MATCH clause successfully finds the starting node
* **Invalid Relationship Type:** If you specify a relationship type that doesn't exist in your graph, the traversal will only include the starting node
* **Memory Limitations:** For large graphs with high connectivity, an out-of-memory error may occur if too many nodes are visited
* **Result Size:** If the BFS traversal returns too many nodes, query execution may be slow or time out; in such cases, try reducing the max\_depth or filtering by relationship types

## Frequently Asked Questions

<AccordionGroup>
  <Accordion title="What is the syntax for calling BFS in FalkorDB?">
    Use `CALL algo.bfs(start_node, max_depth, relationship) YIELD nodes, edges` where start\_node is a matched node, max\_depth is an integer, and relationship is an optional string filter.
  </Accordion>

  <Accordion title="How do I limit BFS to only traverse specific relationship types?">
    Pass the relationship type as the third argument, e.g. `CALL algo.bfs(n, 3, 'FRIEND')`. Pass `null` to traverse all relationship types.
  </Accordion>

  <Accordion title="What happens if my starting node is null?">
    The procedure will raise an error. Always ensure your `MATCH` clause successfully finds the starting node before calling `algo.bfs`.
  </Accordion>

  <Accordion title="When should I use BFS instead of algo.SPpaths?">
    Use **BFS** when you want to explore or discover nodes layer by layer (e.g. friend recommendations). Use **[algo.SPpaths](/algorithms/sppath)** when you need the *weighted* shortest path between two specific nodes.
  </Accordion>

  <Accordion title="How can I avoid memory issues with BFS on large graphs?">
    Set a reasonable `max_depth` value, specify a relationship type filter, and ensure your starting node properties are **indexed** for fast lookup.
  </Accordion>
</AccordionGroup>