12-现实世界的应用

4.6　现实世界的应用

现实世界中有大量问题都可以图来表示。本章已经介绍了图能高效地解决交通网络问题，而很多其他类型的网络都有同样的重要优化问题：电话网络、计算机网络和公用事业（电力、供水等）网络。因此，图算法对于提高电信、航运、交通和公用事业行业的效率至关重要。

零售商必须处理复杂的配送问题。商店和仓库可以被视作顶点，它们之间的距离就是边。算法是一样的。互联网本身就是一个巨大的图，每个连网的设备都是一个顶点，每个有线或无线连接就是一条边。最小生成树和最短路径问题的求解方案不仅可以用于游戏，而且对于企业节省燃料或者电线也同样适用。有一些世界著名的品牌企业通过优化图问题的解法而获得了成功，沃尔玛构建了一个高效的配送网络，谷歌为整个互联网（一张巨大的图）建立了索引，联邦快递找到了一系列能够连通世界所有地址的中转枢纽。

图算法的一些显而易见的应用是社交网络和地图的应用。在社交网络中，人就是顶点，而关系（例如Facebook的朋友圈）就是边。事实上，Facebook的最著名的开发者工具之一就被称为Graph API。在Apple Maps和Google Maps等地图应用中，图算法用于指明方向和计算行程所需的时间。

有一些流行的视频游戏也明确用到了图算法。MiniMetro和Ticket to Ride就是与本章所解问题密切相关的两个游戏示例。