1.2 图的一些应用

图是一个基本概念，广泛存在于计算机科学、生物学、社会学和经济学等领域。下面是图的无数应用中的一些例子。

道路网。当手机的导航软件计算行驶路线时，它在一个表示道路网络的图中进行搜索，图中的顶点表示道路的交汇处，图中的每条边表示一条单独的道路。

万维网（World Wide Web）。万维网可以用有向图来建模，其中的顶点对应于单个的Web页面，边对应于超链接，边的方向是从包含超链接的页面到目标页面。

社交网络。社交网络也可以用图来表示，其中顶点对应于个人，边对应于某种类型的关系。例如，一条边可以表示它的两个顶点为朋友关系，或者表示其中一个顶点是另一个顶点的关注者。在当前流行的社交网络中，哪些建模为无向图更为自然？哪些建模为有向图更为自然？两者都有一些有趣的例子。

优先级约束。图对于那些缺少明显的网络结构的问题也是非常适用的。假设我们必须完成一组受到优先级约束的任务，例如把自己看成是大学一年级的新生，计划按照某种顺序学习几门课程。解决这种问题的一种方法是把本书2.5节描述的拓扑排序算法应用于下面这种图：每个顶点表示专业要求的一门课程，从课程A到课程B的有向边表示学完课程A是学习课程B的先决条件。