描述图

下图是描述社交网络的一种方法：

两个人名字之间的一条线意味着他们认识。如果两个名字之间没有线，那么他们就不认识。这种“互相认识” 关系是双向的；例如，因为奥黛丽认识盖尔，这意味着盖尔也认识奥黛丽。

这个社交网络是 图。姓名是图的 顶点。（如果你只谈论其中一个顶点，那就是 顶点 图。）每条线都是 边，连接两个顶点。我们用 $(u,v)$‍ 对表示连接顶点$u$‍ 和 $v$‍ 的边。因为“彼此认识”关系是双向的，所以这个图表是无向的。无向边 $(u,v)$‍ 与 $(v,u)$‍ 相同。稍后，我们将看到 有向图，其中顶点之间的关系不一定是双向的。在无向图中，两个顶点之间的边，例如奥黛丽和盖尔之间的边，在两个顶点上是 连接，我们说由边连接的顶点是 相邻 或 邻居。 连接在顶点上的边数是顶点的 度 。

奥黛丽和弗兰克不认识。假设弗兰克想要被介绍给奥黛丽。他如何能得到介绍呢？他认识艾米丽，艾米丽认识比尔，比尔认识奥黛丽。我们说，弗兰克和奥黛丽之间有一个 路径 包含三条边。事实上，这是让弗兰克认识奥黛丽的最直接方式；他们之间没有少于三条边的路径。我们将边最少的两个顶点之间的路径称为 最短路径。下面着重标出了这一特定的最短路径：

当路径从特定顶点返回到自身时，这是一个 圈。这个社交网络包含许多圈；其中一个是从奥黛丽到比尔到艾米丽到杰夫到哈瑞到伊利亚纳 最后回到奥黛丽。还有一个包含奥黛丽的圈，比前面那个更小一点：奥黛丽到比尔到戴尔然后回到奥黛丽。你还能找到其他的圈吗？

有时我们会把数值放在边上。例如，在社交网络中，我们可能会使用值来指示两个人彼此了解的程度。这里有另一个例子，让我们以图形的形式表示路线图。假设没有单行道，路线图也是无向图，城市作为顶点，道路作为边，边上的值表示每条道路的距离。例如，这里有个美国东北部的某些州际公路的路线图，边上标有距离，该图不是比例图，如下：

对于边上的数字，我们一般使用 权重 这个术语来表示，边上有权重的图是 带权重图。在路线图的例子中，如果要查找两个位置之间的最短路径，则需要查找两个顶点之间的路径，其中包含两个顶点之间所有路径上的边的权重的最小和。与无权图一样，我们将此类路径称为最短路径。例如，从纽约到康科德，这张图表中最短的路径是从纽约到纽黑文，再到哈特福德，再到斯特布里奇，再到韦斯顿，再到雷丁，再到康科德，总共有289英里。

顶点之间的关系并不总是双向的。例如，在路线图中，可能有单行道。另外，这里有一个图，显示了一个参加冰球的守门员可以穿上的衣服顺序:

现在你会发现，用箭头显示的边是 有向的，我们有一个有向图。在这里，方向表示哪些装备必须放在其他组件之前穿上。例如，从胸垫到毛衣的边表明，胸垫必须放在毛衣之前。顶点旁边的数字显示了许多可能的穿戴设备的顺序，先内衣，然后袜子，然后是压缩短裤，等等，挡板在最后。你可能已经注意到，这个特殊的有向图没有圈；我们称这样的图为 有向无环图, 或 dag。当然，我们可以描绘带权有向图，例如有单行线和道路距离的路线图。

我们关于有向边还有一些不同的术语。我们说有向边离开一个顶点而进入另一个顶点。例如，一个有向边离开胸垫的顶点并进入毛衣的顶点。 如果有向边离开顶点 $u$‍ 进入顶点 $v$‍，我们将它记作$(u,v)$‍，顶点的顺序对有向边是很重要的。 一个顶点离开的有向边数目叫做顶点的 出度，进入的有向边数目叫做入度。

正如你想象的那样，基于对现实世界的建模，图 (包括有向和无向) 有许多应用。

当使用图的时候，我们用边和顶点的集来描述信息，是非常有用的方法。通常用 $V$‍ 表示顶点，用 $E$‍ 表示边。当我们表示图或者在图上运行算法的时候，通常想要在渐近符号中使用顶点和边的数量。例如，假设想要谈论一个运行时间，这个运行时间对于顶点的数量来说是线性的。严格地说来，我们需要说它是 $\mathrm{\Theta }(|V|)$‍，使用符号 $|\cdot |$‍ 来表示集合的大小。但在渐近表示法中使用这个集合大小符号很繁琐，故而我们接受一个惯例，在渐近表示法中，只 在渐近表示法中，简化这个集合大小表示符。所以我们不写作$\mathrm{\Theta }(|V|)$‍，而只写作$\mathrm{\Theta }(V)$‍。要简化$\mathrm{\Theta }(\lg |E|)$‍，我们写作$\mathrm{\Theta }(\lg E)$‍。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。