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