下载掌阅APP，畅读海量书库
立即打开
遍历图是指在图中进行搜索以及收集和分析数据。可以将图想象成一组相互连接的垫脚石路径，其中每个垫脚石代表一个顶点，一个人或多个人在访问该图。要读取或写入一个顶点，人必须站在它的垫脚石上。从这个位置开始，人可以通过边到达相邻的石头/顶点。从新的位置再次出发，人可以再迈一步。请记住：如果两个顶点直接相连，意味着它们之间存在关系，因此遍历是遵循关系链的。
遍历一条边也称为一跳（hop）。遍历一个图可以类比为在游戏棋盘上移动，如图2-8所示。图是一个奇特的游戏棋盘，你可以像在游戏棋盘上移动一样来遍历图。
图2-8：遍历图就像在游戏棋盘上移动一样
在许多棋盘游戏中，当轮到你时，你会通过掷骰子来决定要走或跳多少步。在其他游戏中，你可以遍历整个棋盘直至到达一个特定类型的空间。这类似于遍历图来查找特定类型的顶点。
图的跳数和距离在现实世界的其他情况中也会出现。你可能听说过“六度分离”的理论，该理论认为，每个人与其他人之间最多只需通过六层关系就能连接在一起。如果你使用商务社交应用LinkedIn，当你查看某人的个人资料时，LinkedIn会告诉你他是直接与你相连（一跳），还是通过两跳或三跳相连。
遍历也是在图数据库中进行搜索的方式。遍历图有两种基本方法：一种是先访问每个相邻顶点，然后再继续访问下一层的顶点[广度优先搜索（BFS）]；另一种是沿着单个连接链直到末尾，然后再回溯尝试其他路径[深度优先搜索（DFS）]。第6章会详细介绍这些搜索类型。
BFS意味着先访问你的每个直接邻居，然后再继续搜索下一层的邻居，以此类推。具有并行处理能力的图数据库可以通过同时进行多个遍历来加速BFS。
DFS意味着沿着一条连接链尽可能远地前进，然后再回溯尝试其他路径。BFS和DFS最终都会访问到每个顶点，除非你已经找到了目标顶点并停止搜索。