点击查看第一章
点击查看第三章

第2章

图论
早上闹钟响起，你睁开惺忪的睡眼伸手去拿手机。关掉闹铃的时候，你看到了2条通知。有15个人给你昨晚的推特点了赞，美滋滋，仔细一看，又有3人转发，这可真是棒极了。你的“瞬间网红”体验就是图论的神奇力量（见图2-1）。

热爱工作的你冲向地铁站，赶在车门关上前一瞬间挤了进去。开车了，美好的一天又开始了。
车门开开关关，乘客上上下下。你在换乘站换乘了另一条线路，然后又走了两站，如图2-2所示：
就在你坐着扶梯快要出站的时候，电话响了，是你可爱的妹妹。她说她想去参加下个月爷爷的八十大寿，想买火车票。这个时候你想到既然是爷爷的大寿，那亲戚朋友肯定少不了。于是你的脑海里就规划出了另一个图形：家谱（见图2-3）。

后来，你开始留意各处的图形。社交媒体、交通路线图和电话本到处都是它们的身影。大到宇宙中的星座，小到自然界的分子构成，图形无处不在（见图2-4和图2-5）。
图形可以清楚地表示项目、人员、想法或数据等之间的关系。那么图形的概念又从何而来呢？为了理解这一点，我们来追根溯源一番，了解一下图论和它的数学起源。

学习GraphQL实际上并不需要了解任何图论知识。但是我们认为探究这些概念背后的历史是很有趣的。

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

如图2-6所示，该图形由表示数据点的四个圆组成。在图论术语中，这些圆被称为节点（node）或顶点（vertice）。这些节点之间的线或连接则被称为边（edge），图2-6中有5条边。注1
这样我们可以列一个等式：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）。

当你开始遍历或访问这个图的不同节点时，可以从任意位置开始和结束，并向任意方向移动。数据并不遵循明显的顺序，因此无向图是一种非线性数据结构。接下来，介绍另一种类型的图，有向图（directed graph），如图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。

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

图论的历史

对图论的研究可追溯到1735年的普鲁士柯尼斯堡（现俄罗斯加里宁格勒州首府）。该镇位于普雷格尔河（Pregel River）上，是一个航运枢纽，有两个大岛通过七座桥连接了四块主要陆地，如图2-10所示。
柯尼斯堡（Konigsberg）是一座美丽的小镇，镇上的人们喜欢在桥上散步欢度周末。一直以来，镇上的居民纠结于怎样才能在不经过同一座桥的情况下，依次跨越七座桥。他们走遍小镇试图走过每个岛屿，想尽一切办法不重复经过任一座桥梁，可每次都失败了。万般无奈之下，他们拜访了莱昂哈德 "欧拉（Leonhard Euler）。大名鼎鼎的欧拉是一位多产的瑞士数学家，他一生出版和发表了500多部书籍和论文。
天才很忙，欧拉并不关心那些看起来微不足道的问题。但在多想了一会儿之后，他发现这个问题并不简单，随即也和镇上的居民一样对它产生了兴趣并想要真正搞清楚。欧拉没有写下所有可能的路径，而是决定查看陆地之间的7座桥梁，如图2-11所示。

接下来他将其简化，把桥梁和陆地绘制成后来被称为图的图形，如图2-12所示。
根据图2-12，A和B是由一条边相连接的相邻节点。通过这些边，我们可以计算出每个节点的度数（degree）。节点的度数等于连接该节点的边的数量。如果我们查看七桥问题中的节点，就会发现每个节点的度数都是奇数。

A有5条边连接相邻节点（奇数），B、C、D各有3条边连接相邻节点（奇数）。
因为每个节点的度数都是奇数，欧拉发现不重复经过每座桥是不可能的。一言以蔽之：如果你通过一座桥去一个岛，那么就必须通过另一座桥离开。你说你不想重复经过同一座桥，抱歉，不存在的。
如今，我们把每条边只能访问一次的图称为欧拉路径（Eulerian path）。通过证明，无向图拥有两个奇数度的节点，或者所有节点都是偶数度。我们来看看两个奇数度节点的情况（见图2-13）。

另一个与欧拉相关的概念是环路或欧拉循环（Eulerian cycle）。这种情况是，起始点和结束点相同。每条边只经过一次，但起始点又是结束点（见图2-14）。

柯尼斯堡七桥问题成为图论的第一个定理。欧拉不仅被尊为图论的鼻祖，而且创造了常数e和虚数单位i，甚至变量x之于函数f的数学函数语法f(x)也可以追溯到他。
柯尼斯堡七桥问题是因同一座桥不可以通过超过一次这条规则而产生，但却并未规定必须在何处开始或结束。这就意味着若你试图解决这个问题，那就跳不出无向图这个框。倘若化繁为简，只从特定点开始又会怎样呢？
如果你生活在B岛上，那么你每次走过各个桥就都得从B岛开始。这种情况就是一个有向图，通常称为树（tree）。

树就是图

让我们来看看另一种类型的图：树。树是把节点分层排列的图。当你发现图里有一个根节点的时候，就说明这是一棵树。换句话说，根是树开始的地方，其他节点都作为子节点与根连接。
我们来看一个公司的结构图，这是一个教科书式的树案例。公司CEO高高在上，其他员工都在CEO之下。CEO就是树的根节点，所有其他员工就是树的子节点，如图2-15所示。
树有许多用途，比如可以表示一个家庭的家谱。树还可以映射决策算法（decision-making algorithm），从而帮助程序员高效地访问数据库中的信息。或许有一天，你可以直接把图2-15那个二叉树倒过来，自己出任CEO，走上人生巅峰。
我们可以根据图是否有根节点或者起始节点来判定它是否为树。从根节点开始，树通过边连接各个子节点。当一个节点连接到子节点时，该节点就被称为父节点（parent）。当一个子节点又有子节点时，该节点就被称为分支（branch）。如果一个节点没有子节点，那么这个节点就叫作叶子（leaf）。

节点涵盖了数据点。因此，理解数据在树中的位置就显得尤为重要，这样才能快速地访问数据。为了快速查找数据，我们希望计算单个节点的深度。节点的深度仅仅是指节点离树的根节点有多远。让我们考虑一下A→B→C→D这种树。为了找到节点C的深度，我们来计算C和根节点之间的连接数。C和根节点（A）之间正好有两个连接，所以节点C的深度就是2，同理节点D的深度就是3。
树的层次结构意味着树通常也包括其他树。嵌套在树中的树称为子树。一个HTML页面通常有多个子树。树的根是标记。然后，有两个子树，左侧子树根是

     —friend name
     —friend location
     —friend birthday

me {
    name
    location
    birthday
    friends {
        name
        location
        birthday
    }
}