Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/depth_first_search/
Documentation version: v5.3.2

# 深度优先搜索

本文介绍深度优先搜索算法，并演示如何用 GQL 实现该算法。

## 算法介绍

深度优先搜索通过先深后回溯的方式遍历图结构。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见[深度优先搜索](https://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)。

## 数据模型

为了在 GQL 中实现深度优先搜索算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/depth_first_search/#1_prepare_graph_data)。

## 过程实现[]()

为了计算深度优先搜索结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/depth_first_search/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `source_id`：`INT64`类型。 起始执行 DFS 的点 ID。
- `max_depth`：`INT64`类型，默认值`9223372036854775807`。 DFS 遍历的最大深度限制，默认为不限制。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `done` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 标志 DFS 遍历已完成。
 | `current_id` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前正在探索的点 ID。
 | `current_parent` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | DFS 树中当前点的父点。
 | `current_depth` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前点在 DFS 树中的深度。
 | `visit_idx` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | DFS 遍历顺序的步骤计数。
 | `pick` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 用于选取下一个待探索点的最小堆（最深未访问邻居）。
 | `entered` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点已被压入 DFS 栈。
 | `expanded` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点已被完全展开。
 | `parent` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点在 DFS 树中的父点。
 | `depth` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点的 DFS 深度。
 | `dfs_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储 DFS 遍历顺序和树结构的输出表。

以下步骤概述了该过程的逻辑：

1. 初始化源点：设置`entered`，记录`parent`和`depth`，通过`pick`压入模拟栈。
2. 反复选取最深的未访问邻居（`pick`），标记其为`entered`，设置其`parent`和`depth`并压栈。
3. 当无未访问邻居时，将当前点标记为`expanded`并回溯。
4. 返回所有访问点的 DFS 遍历顺序（`visit_order`、`vertex_id`、`parent_id`、`depth`）。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
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. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/depth_first_search/`：

  - [depth_first_search_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/depth_first_search/depth_first_search_node.csv)：点数据。
  - [depth_first_search_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/depth_first_search/depth_first_search_edge.csv)：边数据。

查看 CSV 内容

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 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: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

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

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现深度优先搜索算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/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. 调用过程[]()

从点`1`开始深度优先搜索，将最大深度设为`6`，返回访问顺序、点 ID、父点 ID 和深度。

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

````

返回：

展开查看返回

````
+-------------+---------+-----------+-------+
| 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     |
+-------------+---------+-----------+-------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。