跳转至

7.1.目标

7.1.目标

  • 了解图是什么,以及如何使用它。
  • 使用多个内部表示来实现图抽象数据类型。
  • 看看如何使用图来解决各种各样的问题

在本章中,我们将研究图。图是比我们在上一章中研究的树更通用的结构;实际上你可以认为树是一种特殊的图。图可以用来表示我们世界上许多有趣的事情,包括道路系统,从城市到城市的航空公司航班,互联网如何连接,甚至是完成计算机科学专业必须完成的课程顺序。我们将在本章中看到,一旦我们有一个问题的好的表示,我们可以使用一些标准图算法来解决,否则可能是一个非常困难的问题。

虽然人们相对容易看路线图并且理解不同地点之间的关系,但计算机没有这样的知识。然而,我们也可以将路线图视为图。当我们这样做时,我们可以让我们的计算机为我们做有趣的事情。如果你曾经使用过一个互联网地图网站,你知道一台计算机可以找到从一个地方到另一个地方最短,最快或最简单的路径。

作为计算机科学的学生,你可能想知道你必须学习的课程,以获得一个学位。图是表示学该课程之前的先决条件和其他相互依存关系的好方法。Figure 1 展示了另一个图。这个代表了在路德学院完成计算机科学专业的课程和顺序。

7.1.目标.figure1