01-图问题

第4章　图问题

图（graph）是一种抽象的数学结构，它通过将问题划分为一组连接的节点对现实世界的问题进行建模。每个节点被称为顶点（vertex），每个连接被称为边（edge）。例如，地铁路线图就可以被视为表示交通网络的图。每个点代表一个地铁站，每条线代表两个地铁站之间的路线。在图的术语中，地铁站被称为“顶点”，路线被称为“边”。

为什么图很有用呢？图不仅有助于我们抽象地思考问题，还可以让我们应用几种易懂、高效的搜索和优化技术。例如，在地铁的示例中，假如我们要知道从一个站到另一个站的最短路径，或者想知道连通所有站点至少需要多少轨道。本章介绍的图算法就能解决这两个问题。此外，图算法还可以应用于任何类型的网络（如计算机网络、配送网络和公用事业网络）问题，而并不仅限于交通网络。用图算法可以解决所有这些网络空间中的搜索和优化问题。