给定一个带权、连通、简单无向图 G，每条边的权重仅为 1 和 2，求 G 在 O(V+E) 中的 MST。
有任何想法吗？
很抱歉问题的措辞，我尽力翻译它。
In Prim 算法 http://en.wikipedia.org/wiki/Prim%27s_algorithm您需要一种存储活动边的方法，以便您可以访问和删除权重最低的边。
通常，重量范围很广，并且有某种堆数据结构 http://en.wikipedia.org/wiki/Binary_heap用于存储边缘。
但是，在本例中，权重为 1 或 2，因此您可以简单地将边存储在 2 个单独的列表中，一个列表用于权重为 1 的边，第二个列表用于权重为 2 的边。
要找到权重最低的边，您只需从第一个列表中取出一条边，除非它是空的，在这种情况下，您可以从第二个列表中取出一条边。
从列表中访问和删除元素的时间复杂度为 O(1)，因此 Prim 的算法将在 O(V+E) 中运行。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
