算法设计。最佳，最有效的解决方案

Question

我有一个小问题想解决。我很想提出最佳解决方案，我认为递归可能是这里的最佳选择。如果您认为我的解决方案是理想的，或者您是否认为有更好的方法，请告诉我。

问题来了: 我有一个城市列表。我想要的算法是确定一个城市与华盛顿特区的度数。每个城市都有一个经过它的高速公路列表。如果一个城市与华盛顿特区共享任何高速公路，那么它与其相差 1 度。如果一个城市不与华盛顿特区共享高速公路，但与华盛顿特区 1 度的城市共享高速公路，那么该城市就是 2 度，儿子。

我正在考虑创建一个高速公路列表，每条高速公路都应该有一个它经过的所有城市的列表。然后我循环遍历所有穿过华盛顿特区的高速公路，对于每条高速公路，我查看它经过的所有城市，然后递归检查每个城市，看看最终有一条高速公路会到达华盛顿特区，这样我就可以得到度数。

你会如何解决这个问题？

Answer 1

你要构建一个图，其中节点是城市，城市 A 和 B 之间有一条无向边当且仅当 A 和 B 之间有高速公路连接。那么度就是最短路径的长度(所有边的长度为 1)在各个城市之间。您可以使用广度优先搜索找到它。

如何枚举边？对于每条高速公路，只需使用两个嵌套循环来查找所有城市对。