广度优先搜索（BFS）

概述

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

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

广度优先搜索（BFS）算法按层遍历图，具体实现步骤如下：

1. 创建一个队列（先进先出）来跟踪已访问的节点。
2. 从选择的起始节点开始，将其入队到队列中，并标记该节点为已访问。
3. 从队列前端出队一个节点，将其所有未访问的邻居入队到队列中，并标记它们为已访问。如果有多个未访问邻居，任意选择一个或按照某种确定的顺序进行选择。
4. 重复第3步，直到队列为空。

下面是以BFS方式遍历图的示例，以节点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: ['A'],
    direction: 'out',
    traverse_type: 'bfs'
  },
  return_params: {
    file: {
      filename: "visited_nodes"
    }
  }
})

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

结果：

node,parent
D,A
F,E
B,A
A,A
E,B
C,F