GraphQL 学习指南 (15):图论 2.3

阅读数:8 2019 年 12 月 15 日 19:25

GraphQL学习指南(15):图论 2.3

(树就是图)

内容简介
为什么 GraphQL 是 Ajax 诞生以来具创新性的数据获取技术?GraphQL 通过为 API 提供查询语言和用以完成查询的运行状态,提供了对 REST 和特定页面服务架构的替代方案。借助这《GraphQL 学习指南》,Alex Banks 和 Eve Porcello 为希望开始使用 GraphQL 的前端 Web 开发人员、后端工程师以及项目或产品经理提供了一条清晰的学习路径。你将先后探索图论、图数据结构和 GraphQL 类型,之后在实际项目中学习如何为照片共享应用构建 schema。
《GraphQL 学习指南》还将向你介绍 Apollo Client,可用来将 GraphQL 连接到你的用户界面。

让我们来看看另一种类型的图:树。树是把节点分层排列的图。当你发现图里有一个根节点的时候,就说明这是一棵树。换句话说,根是树开始的地方,其他节点都作为子节点与根连接。

我们来看一个公司的结构图,这是一个教科书式的树案例。公司 CEO 高高在上,其他员工都在 CEO 之下。CEO 就是树的根节点,所有其他员工就是树的子节点,如图 2-15 所示。

树有许多用途,比如可以表示一个家庭的家谱。树还可以映射决策算法(decision-making algorithm),从而帮助程序员高效地访问数据库中的信息。或许有一天,你可以直接把图 2-15 那个二叉树倒过来,自己出任 CEO,走上人生巅峰。

我们可以根据图是否有根节点或者起始节点来判定它是否为树。从根节点开始,树通过边连接各个子节点。当一个节点连接到子节点时,该节点就被称为父节点(parent)。当一个子节点又有子节点时,该节点就被称为分支(branch)。如果一个节点没有子节点,那么这个节点就叫作叶子(leaf)。

GraphQL学习指南(15):图论 2.3

图 2-15:公司结构图

节点涵盖了数据点。因此,理解数据在树中的位置就显得尤为重要,这样才能快速地访问数据。为了快速查找数据,我们希望计算单个节点的深度。节点的深度仅仅是指节点离树的根节点有多远。让我们考虑一下 A→B→C→D 这种树。为了找到节点 C 的深度,我们来计算 C 和根节点之间的连接数。C 和根节点(A)之间正好有两个连接,所以节点 C 的深度就是 2,同理节点 D 的深度就是 3。

树的层次结构意味着树通常也包括其他树。嵌套在树中的树称为子树。一个 HTML 页面通常有多个子树。树的根是 <html> 标记。然后,有两个子树,左侧子树根是 <head>,右侧子树的根就是 <body>。从这里开始,<header><footer><div> 都是不同子树的根。多个嵌套也就产生了多个子树,如图 2-16 所示。

GraphQL学习指南(15):图论 2.3

图 2-16:一个 HTML 树

正如树是一种特定类型的图一样,二叉树(binary tree)也是一种特定类型的树。二叉树的意思是每个节点的子节点数都不超过两个。当谈到二叉树时,通常指的是二叉搜索树(binary search trees)1。二叉搜索树是遵循特定排序规则的二叉树。排序规则和树结构可帮助我们快速找到所需的数据。图 2-17 展示了一个二叉搜索树的例子。

1 参见 Vaideehi Joshi 的博客文章“Leaf It Up to Binary Trees”。

GraphQL学习指南(15):图论 2.3

图 2-17:二叉搜索树

它同样拥有一个根节点,并且遵守每个节点不超过两个子节点的规则。假设我们想要找到节点 15。如果没有二叉搜索树,我们需要遍历每个节点,直至找到节点 15。也许我们会幸运地沿着正确的分支走下去,可谁又能保证幸运女神每次都会眷顾我们呢,碰个满头包然后回去一个个找才是最真实的情况。

利用二叉搜索树,通过对左右节点规则的理解,我们可以很快地定位节点 15。如果我们从根节点(9)开始遍历,我们会问“15 比 9 大还是小?”如果小于,我们就找它左边的节点。如果大于,就找右边。这样一来,我们便排除了树中一半的节点。然后我们找到了节点 20,我们再次考虑 15 和 20 的大小关系,于是我们再继续找它的左子节点。这样,又有一半的节点不用考虑。然后我们找到了节点 13,15 大于 13,因此我们通过寻找右侧子节点找到了它。通过不断地使用左右节点判断来排除不合适选项,我们可以更快地找到所需的数据。

GraphQL学习指南(15):图论 2.3

购书地址 https://item.jd.com/12639300.html?dist=jd

评论

发布