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

# Depth First Search

## Algorithm introduction

Depth-first search explores graph paths by expanding one branch deeply before backtracking.

Compute a classic iterative depth-first search on a directed graph whose node primary key is id. Starting from source_id, each discovered node is visited once, and traversal can be bounded by max_depth.

For more information, see [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search).

## Data model

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

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

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

## Procedure implementation[]()

To compute Depth First Search results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/depth_first_search/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `source_id`: `INT64`. ID of the source node to start DFS from.
- `max_depth`: `INT64` (default: `9223372036854775807`). Maximum depth limit for DFS traversal. Default is effectively unlimited.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `done` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Flag indicating DFS traversal has finished.
 | `current_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Node ID of the node currently being explored.
 | `current_parent` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Parent of the currently explored node in the DFS tree.
 | `current_depth` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Depth of the current node in the DFS tree.
 | `visit_idx` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Step counter for DFS traversal order.
 | `pick` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Min-heap for selecting the next node to explore (deepest unvisited neighbor).
 | `entered` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node flag: node has been pushed onto the DFS stack.
 | `expanded` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node flag: node has been fully explored.
 | `parent` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node parent in the DFS tree.
 | `depth` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node DFS depth.
 | `dfs_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing DFS traversal order and tree structure.

The following steps outline the logic of the procedure:

1. Initialize the source node: set `entered`, record `parent` and `depth`; push onto the simulated stack via `pick`.
2. Repeatedly select the deepest unvisited neighbor (`pick`), mark it `entered`, set its `parent` and `depth`, and push it.
3. When no unvisited neighbor exists, mark the current node `expanded` and backtrack.
4. Return the DFS traversal order (`visit_order`, `vertex_id`, `parent_id`, `depth`) for all visited nodes.

## 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 depth_first_search_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

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

  - [depth_first_search_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/depth_first_search/depth_first_search_node.csv): Node data.
  - [depth_first_search_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/depth_first_search/depth_first_search_edge.csv): Edge data.

Preview the CSV files

depth_first_search_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

depth_first_search_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

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 #depth_first_search_graph TYPED depth_first_search_graph_type

````

````
'''
USE #depth_first_search_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/depth_first_search/depth_first_search_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/depth_first_search/depth_first_search_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

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

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

````

The expected `node_count` is `24`. 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 Depth First Search algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/depth_first_search/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE depth_first_search(
  source_id INT64,
  max_depth INT64 DEFAULT 9223372036854775807
)
RETURNS (visit_order INT64, node_id INT64, parent_id INT64, depth INT64)
COMMENT "Compute a classic iterative depth-first search on a directed graph whose vertex primary key is id. Starting from source_id, each discovered vertex is visited once, and traversal can be bounded by max_depth."
AS {
  VALUE done BOOLEAN = false
  VALUE current_id INT64 = 0
  VALUE current_parent INT64 = 0
  VALUE current_depth INT64 = 0
  VALUE visit_idx INT64 = 0

  VALUE pick TopKAgg<1, depth INT64 DESC, node_id INT64 DESC, parent_id INT64 ASC>

  NODE VALUE entered OrAgg = false
  NODE VALUE expanded OrAgg = false
  NODE VALUE parent MaxAgg<INT64> = 0
  NODE VALUE depth MaxAgg<INT64> = 0

  TABLE dfs_table TYPED TABLE {
    visit_order INT64,
    node_id INT64,
    parent_id INT64,
    depth INT64
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@entered = false
    SET n.@expanded = false
    SET n.@parent = 0
    SET n.@depth = 0
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@entered = true
    SET s.@expanded = false
    SET s.@parent = source_id
    SET s.@depth = 0
  }

  WHILE done = false THEN {
    SET @pick.clear()

    MATCH (n)
    WHERE n.@entered = true AND n.@expanded = false
    PER NODE (n) {
      SET @pick += RECORD{depth: n.@depth, node_id: n.id, parent_id: n.@parent}
    }

    IF @pick.size() = 0 THEN {
      SET done = true
    }
    ELSE {
      SET current_id = @pick.min().node_id
      SET current_parent = @pick.min().parent_id
      SET current_depth = @pick.min().depth
      SET visit_idx = visit_idx + 1

      MATCH (u)
      WHERE u.id = current_id
      PER NODE (u) {
        SET u.@expanded = true
      }

      EXPORT visit_idx, current_id, current_parent, current_depth INTO dfs_table

      IF current_depth < max_depth THEN {
        MATCH (u)-[e]->(v)
        WHERE u.id = current_id AND v.@entered = false
        PER PATH {
          SET v.@entered += true
        }
        PER NODE (v) {
          SET v.@expanded = false
          SET v.@parent = current_id
          SET v.@depth = current_depth + 1
        }
      }
    }
  }

  FOR r IN dfs_table
  RETURN
    r.visit_order AS visit_order,
    r.node_id AS node_id,
    r.parent_id AS parent_id,
    r.depth AS depth
  ORDER BY visit_order ASC
}
'''

````

### 3. Call your procedure[]()

Start depth-first search at node `1` with a maximum depth of `6`. Return the visit order, node ID, parent ID, and depth.

````
USE #depth_first_search_graph CALL depth_first_search(1, 6) RETURN visit_order, node_id, parent_id, depth

````

Returns:

Expand to view results

````
+-------------+---------+-----------+-------+
| visit_order | node_id | parent_id | depth |
+-------------+---------+-----------+-------+
| 1           | 1       | 1         | 0     |
| 2           | 5       | 1         | 1     |
| 3           | 9       | 5         | 2     |
| 4           | 13      | 9         | 3     |
| 5           | 16      | 13        | 4     |
| 6           | 19      | 16        | 5     |
| 7           | 22      | 19        | 6     |
| 8           | 21      | 19        | 6     |
| 9           | 18      | 16        | 5     |
| 10          | 15      | 13        | 4     |
| 11          | 12      | 9         | 3     |
| 12          | 14      | 12        | 4     |
| 13          | 17      | 14        | 5     |
| 14          | 20      | 17        | 6     |
| 15          | 10      | 9         | 3     |
| 16          | 8       | 5         | 2     |
| 17          | 11      | 8         | 3     |
| 18          | 6       | 5         | 2     |
| 19          | 4       | 1         | 1     |
| 20          | 7       | 4         | 2     |
| 21          | 3       | 1         | 1     |
| 22          | 2       | 1         | 1     |
+-------------+---------+-----------+-------+

````

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.