最小续航里程的电动车需要穿越每个城市
我对这个任务有点卡住了。
我们有一个矩阵，其中包含每个城市（60 个城市）之间的距离。我们必须乘坐电动汽车至少穿过每个城市一次。每个城市都有汽车充电站。我们可以在一个城市停留多少次没有限制。
我必须找到汽车需要的一次充电的最小范围，以便我们可以穿过每个城市。
我应该如何遇到这个任务？
回答
更新：
虽然MST（最小生成树）适用于这个问题，但它可能1没有最佳时间复杂度。该问题应考虑为MSBT（最小瓶颈生成树），对于该问题，存在边数方面具有线性时间复杂度的算法，例如Camerini's_algorithm。
您正在寻找 MST 的最大边缘。有寻找MST，其中有许多知名的算法Kruskal的和普里姆的（这btilly在他的回答使用）是最容易实现的。
很容易看出，为什么MST的最大边足以穿越每一个城市：你可以穿越所有城市，在每个城市充满电，只行驶属于树的道路。
至少需要 MST 的最大边的范围，否则您将无法访问此边连接的两个城市。这可以从克鲁斯卡尔算法的构造方式看出。如果只取小于 MST 最大边的边，那么 Kruskal 算法将无法将所有顶点连接成单个连接组件。
让我们假设有一个最小生成树，其边大于其他（最小或非最小）生成树的最大边。然后我们将尝试用较小的替换它。为此，首先删除这条边。现在我们剩下两组顶点。第二棵树必须用一条边连接这些集合。让我们将这条边添加到第一棵树中。由于这条边比被删除的边小，那么我们得到了一棵边总和小于最小生成树的树，所以这棵树一开始就不能是最小生成树，这是矛盾的。综上所述：
- 较大的生成树不能有较小的最大边
- 树的每个最小生成的所有最大边都相同
第一条语句意味着 MST 是寻找解的树，第二条语句意味着使用哪种算法来查找 MST 并不重要