加权图和应用

如果每条边都分配了权重，那么图就是加权图。加权图有许多实际应用。

上图假设该图代表城市之间的航班数量。您可以应用 BFS 来查找两个城市之间的最少航班数量。假设边代表城市之间的行驶距离，如下图所示。如何找到连接所有城市的最小总距离？如何找到两个城市之间的最短路径？本章将解答这些问题。前者称为最小生成树（MST）问题，后者称为最短路径问题。

上一章介绍了图的概念。您学习了如何使用边数组、边列表、邻接矩阵和邻接列表来表示边，以及如何使用 Graph 接口、AbstractGraph 类和 AbstractGraph 类和

UnweightedGraph 类。前面的章节还介绍了图遍历的两种重要技术：深度优先搜索和广度优先搜索，并应用遍历来解决实际问题。下面的文章将介绍加权图。您将学习在 post 中查找最小生成树的算法以及在 post 中查找最短路径的算法。

以上是加权图和应用的详细内容。更多信息请关注PHP中文网其他相关文章！