概述
图遍历(Graph Traversal)是一种系统性的搜索技术,用于访问和探索图中的所有节点。图遍历的主要目标是发现和检查图的结构和连接关系。图遍历有两种常见的策略:
- 广度优先搜索(Breadth-First Seach, BFS)
- 深度优先搜索(Depth-First Seach, DFS)
深度优先搜索(DFS)算法基于回溯(Backtracking)原则,具体实现步骤如下:
- 创建一个栈(后进先出)来跟踪已访问的节点。
- 从选择的起始节点开始,将其推入栈,并标记该节点为已访问。
- 将位于栈顶的节点的任意一个未访问邻居推入栈,并标记为已访问。如果有多个未访问邻居,任意选择一个或按照某种确定的顺序进行选择。
- 重复第3步,直到没有更多未访问的邻居可以推入栈。
- 当没有新节点可以访问时,通过从栈中弹出顶部节点回溯到前一个节点(即当前节点是从哪个节点探索而来的)。
- 重复第3、4和5步,直到栈为空。
下面是以DFS方式遍历图的示例,以节点A作为起始节点,并假定按字母顺序(A~Z)访问邻居节点:
![](https://img.ultipa.cn/draw/draw_9649268c928a4549953d069be862a609.jpg?v='1691377192398')
特殊说明
- 只有与起始节点在同一个连通分量中的节点才能被遍历。不同连通分量中的节点将不会出现在结果中。
语法
- 命令:
algo(traverse)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | _id / _uuid |
/ | / | 否 | 遍历图的起始节点的ID/UUID |
direction | string | in , out |
/ | 是 | 遍历图时遵循的边方向 |
traverse_type | string | dfs |
bfs |
否 | 以DFS方式遍历图时,保持此项为dfs |
示例
![](https://img.ultipa.cn/draw/draw_6bbb8777500c4df6a1f62ee19cfbd821.jpg?v='1693899454238')
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id,_id |
访问的节点(toNode),以及是从哪个节点访问的(fromNode) |
algo(traverse).params({
ids: ['B'],
direction: 'in',
traverse_type: 'dfs'
}).write({
file: {
filename: 'result'
}
})
结果:result
F,C
E,F
C,A
B,B
A,B