Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/bfs/
Documentation version: v5.3.2

# Breadth-First Search (BFS)

## Algorithm introduction

Breadth-First Search explores a graph level by level from a given source node. In an unweighted graph, BFS computes the shortest-path distance (in number of hops) from the source to all reachable nodes and identifies which nodes are reachable.

This implementation uses iterative [label propagation](https://en.wikipedia.org/wiki/Label_propagation_algorithm) with an active set to implement BFS. The algorithm works as follows:

1. Initialize the distance of the source node to `0` and mark it visited; all other nodes have "infinite" distance and are unvisited.
2. 

Repeatedly expand from the current active set: for each node `u` taken from the current active set, it looks at all of its neighbors (`v`). If a neighbor `v` has not been visited yet, the algorithm does three things:

  1. Marks `v` as visited to avoid processing it again.
  2. Sets the distance to `v` as `distance[u] + 1`. This is the core logic: the path from the source node to `v` is one step longer than the path to `u`.
  3. Adds `v` to a new active set for the next iteration.

3. 

Once all nodes in the current active set have been processed, the current active set is replaced by the new one. The process repeats. When the new active set is empty, it means there are no more reachable, unvisited nodes, and the algorithm stops.

For more information about BFS, see [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search).

## Data model

To implement the BFS algorithm in GQL, the following data model is used to create a graph type:

- Persons are represented by nodes of type `Person`.
- Relationships between persons are represented by edges of type `Knows`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/bfs/#1_prepare_graph_data).

## Procedure implementation

To compute hop distances from a single source and mark reachability, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created to implement BFS with an active set.

For the complete definition of the procedure, see [Create a procedure](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/bfs/#2_create_a_procedure). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameter:

- `sid`: The source node ID.

Additionally, the following variables are defined within the procedure:

 | Variable | Type | Description
 | `min_distance` | Node-attached [MinAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/min_agg/) | The hop distance per node. Initialized to a large value (e.g., `999`); the source node is set to `0`. MinAgg ensures a node keeps the smallest distance seen so far.
 | `visited` | Node-attached [OrAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | Whether a node is visited. Once it is visited, it remains `true`.
 | `new_active` | Global [OrAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | Indicates whether any node was newly visited in the current iteration; controls loop termination.
 | `v_set` | [Active set variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | The active set of nodes to expand in the next iteration.
 | `output_file` | [File variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/file-variable/) | A file variable to collect the final results for output.

The following steps outline the logic of the procedure:

1. Initialize the source node: set its `visited` to `true` and `min_distance` to `0`. Initialize the active set `v_set` with the source node.
2. 

Repeat while `new_active` is `true`:

  1. Reset `new_active` to `false`.
  2. For each edge (`v -> d`) where `v` is in `v_set` and `d` is not yet visited, set `visited[d] = true`, update the value of `min_distance[d]` based on `min_distance[d] = min(min_distance[d], min_distance[v] + 1)`, and set `new_active = true`.
  3. Set `v_set` to all nodes `d` updated in this iteration (the next active set).

3. 

After convergence (no updates in an iteration), export each node’s ID, `min_distance`, and `visited` into `output_file` and return them.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS bfs_graph_type AS {
    NODE Person (LABEL Person {id INT PRIMARY KEY, name STRING}),
    EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY ()}]->(Person)
}
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/bfs/` under your deployment directory:

  - [bfs_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/bfs/bfs_node.csv): Node data.
  - [bfs_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/bfs/bfs_edge.csv): Edge data.

Preview the CSV files

bfs_node.csv

````
id,name
1,Alice
2,Bob
3,Charlie
4,David

````

bfs_edge.csv

````
src,dst
1,2
2,3
1,4
3,4
4,2

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #bfs_graph TYPED bfs_graph_type

````

````
'''
USE #bfs_graph IMPORT INTO GRAPH {
    NODE (v@Person {id: id, name: name}) FROM DATAFILE {
      PATH: "file:///examples/algorithms/bfs/bfs_node.csv",
      FORMAT: "CSV",
      DELIMITER: ','
    },
    EDGE (id: src)-[e@Knows{}]->(id: dst) FROM DATAFILE {
      PATH: "file:///examples/algorithms/bfs/bfs_edge.csv",
      FORMAT: "CSV",
      DELIMITER: ','
    }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #bfs_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The expected `node_count` is `4`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure

Create a procedure to implement the BFS algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/bfs/#procedure_implementation).

````
'''
CREATE OR REPLACE PROCEDURE bfs(sid INT64) RETURNS () AS {
    VALUE      v_set        ACTIVE_SET
    VALUE      new_active   OrAgg = true
    NODE VALUE min_distance MinAgg<INT> = 999
    NODE VALUE visited      OrAgg = false
    FILE       output_file  {id INT64, distance INT64, visited BOOL} = DATAFILE {
                                  PATH: "file:///examples/algorithms/bfs/output",
                                  FORMAT: "CSV"
                                  }

    // Initialize source
    MATCH (s@Person) WHERE s.id = sid
    FINALLY {
        SET v_set = s
    }

    MATCH (s)
    WHERE s IN v_set
    PER NODE (s) {
      SET s.@visited = true
      SET s.@min_distance = 0
    }

    // Iterate until no updates
    WHILE @new_active = true THEN {
      SET @new_active = false
      MATCH (v)-[e]-(d)
      WHERE d.@visited = false AND v IN v_set
      PER PATH {
        SET d.@visited += true
        SET d.@min_distance += v.@min_distance + 1   // MinAgg applies min()
        SET @new_active += true                      // OrAgg turns true if any update happens
        }
      FINALLY {
        SET v_set = d
        }
    }

    // Collect results
    MATCH (s)
    PER NODE (s) {
      EXPORT s.id, s.@min_distance, s.@visited INTO output_file
    }
}
'''

````

### 3. Call your procedure

Call the procedure to compute hop distances from source node `1`.

````
USE #bfs_graph CALL bfs(1) FINISH

````

This call writes the results to CSV files and does not return a table in the console.

On the Docker host, open the CSV files in `examples/algorithms/bfs/output/` under your deployment directory. Example contents:

````
"id","distance","visited"
1,0,true
2,1,true
3,2,true
4,1,true

````

Write results to a graph

If you want to persist BFS results in a graph instead of only exporting to files, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/):

- Export BFS result fields to a table variable first (typically `id`, `distance`, and `visited`).
- For a remote graph, batch the table with `table_split(...)` and send `USE + INSERT` statements through `nebula_exec`.

When adapting the examples from that topic, define the target graph type to include BFS result properties (for example, `distance` and `visited` on `Person`).