GraphQL 学习指南 (13):图论 2.1

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

GraphQL学习指南(13):图论 2.1

(图论相关词汇)

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

顾名思义,图论是对图形的研究。图论是用来表示相互连接的对象的集合。你可以将图形看作一个对象,它包含数据点(data point)和连接(connection)。在计算机科学中,图形常用来描述数据网络。常见的图形结构见图 2-6。

GraphQL学习指南(13):图论 2.1

图 2-6:图

如图 2-6 所示,该图形由表示数据点的四个圆组成。在图论术语中,这些圆被称为节点(node)或顶点(vertice)。这些节点之间的线或连接则被称为边(edge),图 2-6 中有 5 条边。1

1 更多关于节点和边的内容参见 Vaidehi Joshi 的博客:“A Gentle Introduction to Graph Theory”( https://dev.to/vaidehijoshi/a-gentle-introduction-to-grph-theory )。

这样我们可以列一个等式:G=(V,E)

让我们从最简单的缩写开始,G 代表图形,V 代表一组顶点或节点。就图 2-6 来说,V 将等于以下内容:

复制代码
V = {1, 2, 3, 4}

E 代表一组边。通常采用一对节点代表一条边。

复制代码
E = { {1, 2},
{1, 3},
{1, 4},
{2, 4},
{3, 4} }

那么如果我们将这个边集合重新排序会发生什么呢?举例如下:

复制代码
E = { {4, 3},
{4, 2},
{4, 1},
{3, 1},
{2, 1} }

在这种情况下,图形没有发生任何变化,如图 2-7 所示。

方程依然表示这个图形,因为节点之间不存在方向和层次结构。在图论当中,我们称之为无向图(undirected graph)。边或数据点之间的连接就被称为无序对(unordered pair)。

GraphQL学习指南(13):图论 2.1

图 2-7:对边集合重新排序后的图

当你开始遍历或访问这个图的不同节点时,可以从任意位置开始和结束,并向任意方向移动。数据并不遵循明显的顺序,因此无向图是一种非线性数据结构。接下来,介绍另一种类型的图,有向图(directed graph),如图 2-8 所示。

GraphQL学习指南(13):图论 2.1

图 2-8:有向图

节点数相同,而边却有所不同。连接它们的不是线,而是箭头。该图中的节点之间存在方向或流。为了表示它,我们使用以下形式:

复制代码
V = {1, 2, 3, 4}
E = ( {1, 2},
{1, 3}
{3, 4} )

总之,方程就可以表示为:

复制代码
G = ( {1, 2, 3, 4},
({1, 2}, {1, 3}, {3, 4}) )

请注意,我们用圆括号将这些数据对包裹起来,而没有采用花括号。圆括号表示这些边是有序对。无论什么时候,只要边是有序对,那么这个图就是一个有向图。如果我们对这些有向图进行重新排列会发生什么呢?会和无向图一样吗?

复制代码
G = ( {1, 2, 3, 4},
( {4, 3}, {3, 1}, {1, 2} ) )

结果显示,以节点 4 作为根节点的情况下,图形与原来相比有了很大的不同,见图 2-9。

GraphQL学习指南(13):图论 2.1

图 2-9:新生产的有向图

这时如果要遍历该图,那么就需要从节点 4 开始,然后按照箭头的方向依次访问图形的每个节点。为了更容易理解遍历,需要描绘从一个节点到另一个节点的物理路径。实际上,物理路径正是图论概念产生的原因。

GraphQL学习指南(13):图论 2.1

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

评论

发布