仅查找权重为1和2的生成树的算法 [英] Algorithm for finding a spanning tree with weights of 1 and 2 only

问题描述

给定一个加权的，连通的，简单的无向图G，在每条边上权重只有1和2，找到O中的G的MST（V + E）。
有什么想法？

对于这个问题的表述抱歉，我尽可能地尽力翻译它。 Prim的算法，您需要一种存储活动边的方式，以便您可以访问和删除权重最低的边。通常情况下，权重范围和某种堆数据结构用于存储边缘。

然而，在这种情况下，权重是1或2，所以您可以简单地将边缘存储在2个单独的列表中，其中一个用于加权为1的边，第二个用于边与重量2。

要找到最低重量的边缘，只需从第一个列表中选取一个，除非它是空的，在这种情况下，您会从第二个列表。

从列表中访问和删除一个元素是O（1），所以Prim的算法将运行在O（V + E）中。

Given a weighted, connected, simple undirected graph G with weights of only 1 and 2 on each edge, find the MST of G in O(V+E). Any ideas?

Sorry for the phrasing of the question, I tried translating it as best as I could.

解决方案

In Prim's algorithm you need a way of storing active edges such that you can access and delete the edge with lowest weight.

Normally there are a wide range of weights and some kind of heap data structure is used to store the edges.

However, in this case, the weights are either 1 or 2, and so you can simply store the edges in 2 separate lists, one for edges with weight 1, and the second for edges with weight 2.

To find the edge with lowest weight you simply take one from the first list, unless it is empty, in which case you take an edge from the second list.

Accessing and deleting an element from a list is O(1) so Prim's algorithm will run in O(V+E).

这篇关于仅查找权重为1和2的生成树的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！