给定一个无向加权图 G = (V,E)。每个顶点代表一个城市，连接 a 和 b 的边的权重是完成在城市 a 和城市 b 之间建立高速路线所需的年数。描述一种算法，该算法将找到一个人可以在图中任意两个城市之间旅行的最少年数。路线是同时建立的，所以如果我们有三个城市 a、b 和 c 以及 a 和 b 之间的一条边，权重为 1，b 和 c 之间的另一条边，权重为 2，那么输出应该是 2。
问问题
99 次
1 回答
1
上面的评论为您指出了正确的答案，在我看来，这听起来像是一个经典的 Prim 算法问题。http://en.wikipedia.org/wiki/Prim's_algorithm
于 2012-06-01T02:28:56.277 回答