深度优先搜索（DFS）

概述

图遍历（Graph Traversal）是一种系统性的搜索技术，用于访问和探索图中的所有节点。图遍历的主要目标是发现和检查图的结构和连接关系。图遍历有两种常见的策略：

• 广度优先搜索（Breadth-First Seach, BFS）
• 深度优先搜索（Depth-First Seach, DFS）

深度优先搜索（DFS）算法基于回溯（Backtracking）原则，具体实现步骤如下：

1. 创建一个栈（后进先出）来跟踪已访问的节点。
2. 从选择的起始节点开始，将其推入栈，并标记该节点为已访问。
3. 将位于栈顶的节点的任意一个未访问邻居推入栈，并标记为已访问。如果有多个未访问邻居，任意选择一个或按照某种确定的顺序进行选择。
4. 重复第3步，直到没有更多未访问的邻居可以推入栈。
5. 当没有新节点可以访问时，通过从栈中弹出顶部节点回溯到前一个节点（即当前节点是从哪个节点探索而来的）。
6. 重复第3、4和5步，直到栈为空。

下面是以DFS方式遍历图的示例，以节点A作为起始节点，并假定按字母顺序（A~Z）访问邻居节点：

特殊说明

• 只有与起始节点在同一个连通分量中的节点才能被遍历。不同连通分量中的节点将不会出现在结果中。

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"G", _to:"D"}, {_from:"A", _to:"D"}, {_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"E", _to:"F"}, {_from:"F", _to:"C"}, {_from:"C", _to:"A"}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_trv：

CALL hdc.graph.create("hdc-server-1", "hdc_trv", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_trv", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：traverse

文件回写

CALL algo.traverse.write("hdc_trv", {
  params: {
    return_id_uuid: "id",
    ids: ['B'],
    direction: 'in',
    traverse_type: 'dfs'
  },
  return_params: {
    file: {
      filename: "visited_nodes"
    }
  }
})

algo(traverse).params({
  projection: "hdc_trv",
  return_id_uuid: "id",
  ids: ['B'],
  direction: 'in',
  traverse_type: 'dfs'
}).write({
  file: {
    filename: "visited_nodes"
  }
})

结果：

nodes
B,A,C,F,E,