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 with an active set to implement BFS. The algorithm works as follows:

Initialize the distance of the source node to 0 and mark it visited; all other nodes have "infinite" distance and are unvisited.
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.
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.

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.

Procedure implementation¶

To compute hop distances from a single source and mark reachability, a procedure is created to implement BFS with an active set.

For the complete definition of the procedure, see 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	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	Whether a node is visited. Once it is visited, it remains `true`.
`new_active`	Global OrAgg aggregator value variable	Indicates whether any node was newly visited in the current iteration; controls loop termination.
`v_set`	Active set variable	The active set of nodes to expand in the next iteration.
`output_file`	File variable	A file variable to collect the final results for output.

The following steps outline the logic of the procedure:

Initialize the source node: set its visited to true and min_distance to 0. Initialize the active set v_set with the source node.
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).
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 to check where to run commands and how the directory is mounted.

1. Prepare graph data¶

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)
}
'''

Download these CSV files and save them with their original names in examples/algorithms/bfs/ under your deployment directory:
- bfs_node.csv: Node data.
- 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
```

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 before continuing.

2. Create a procedure¶

Create a procedure to implement the BFS algorithm. For more information about the procedure, see 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:

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).