概述
图遍历(Graph Traversal)是一种系统性的搜索技术,用于访问和探索图中的所有节点。图遍历的主要目标是发现和检查图的结构和连接关系。图遍历有两种常见的策略:
- 广度优先搜索(Breadth-First Seach, BFS)
- 深度优先搜索(Depth-First Seach, DFS)
广度优先搜索(BFS)算法按层遍历图,具体实现步骤如下:
- 创建一个队列(先进先出)来跟踪已访问的节点。
- 从选择的起始节点开始,将其入队到队列中,并标记该节点为已访问。
- 从队列前端出队一个节点,将其所有未访问的邻居入队到队列中,并标记它们为已访问。如果有多个未访问邻居,任意选择一个或按照某种确定的顺序进行选择。
- 重复第3步,直到队列为空。
下面是以BFS方式遍历图的示例,以节点A作为起始节点,并假定按字母顺序(A~Z)访问邻居节点:

特殊说明
- 只有与起始节点在同一个连通分量中的节点才能被遍历。不同连通分量中的节点将不会出现在结果中。
示例图

在一个空图中运行以下语句定义图结构并插入数据:
INSERT (A:default {_id: "A"}),
(B:default {_id: "B"}),
(C:default {_id: "C"}),
(D:default {_id: "D"}),
(E:default {_id: "E"}),
(F:default {_id: "F"}),
(G:default {_id: "G"}),
(A)-[:default]->(B),
(A)-[:default]->(D),
(B)-[:default]->(E),
(C)-[:default]->(A),
(E)-[:default]->(F),
(F)-[:default]->(C),
(G)-[:default]->(D);
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
上,并命名为 my_hdc_graph
:
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}
hdc.graph.create("my_hdc_graph", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}).to("hdc-server-1")
参数
算法名:traverse
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
---|---|---|---|---|---|
ids |
_id |
/ | / | 否 | 通过_id 指定遍历的起点 |
uuids |
_uuid |
/ | / | 否 | 通过_uuid 指定遍历的起点 |
direction |
String | in , out |
/ | 是 | 指定遍历时的边方向,in 表示仅遍历入边,out 表示仅遍历出边 |
traverse_type |
String | bfs |
bfs |
是 | 以BFS方式遍历图时,设置该项为bfs |
return_id_uuid |
String | uuid , id , both |
uuid |
是 | 在结果中使用_uuid 、_id 或同时使用两者来表示点 |
文件回写
CALL algo.traverse.write("my_hdc_graph", {
return_id_uuid: "id",
ids: ['A'],
direction: 'out',
traverse_type: 'bfs'
}, {
file: {
filename: "visited_nodes"
}
})
algo(traverse).params({
projection: "my_hdc_graph",
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