这就是问题所在。
给出了一个加权无向连通图 G。权重是恒定的。任务是提出一种算法,该算法将找到满足这两个条件(按优先级排序)的 G 的生成树的总权重:
- 生成树必须具有相同权重的最大边数(实际重复的权重值无关紧要);
- 应该最小化总的生成树权重。这意味着,例如,权重为 120 的生成树 T1 应优先于权重为 140 且权重为大多数 4 条边具有相同的权重(这四个边的权重为 8)。
我已经坚持了很长一段时间了。我已经为图实现了Boruvka的MST搜索算法,现在我不确定是否应该在找到MST之后执行任何操作,或者最好修改MST-search算法本身。
欢迎任何建议!