0

我有一个ArrayList<Edge>我必须删除重复值的地方。 Edge类如下

class Edge
{
    int srcNode;
    int destNode;
    double edgeWeight;
}

我想计算一个图的最小生成树来实现Krushkal 算法。为了计算，我必须Edge从列表中删除所有重复的 s。那么哪种算法最适合从这种具有 srcNode、destNode 和 edgeWeight 的数据结构中删除重复值。

4

2 回答 2

1

Edges您可以在 的基础上创建二叉搜索树edgeWeight。在插入 BST 时，请记住一件事是检查带有 edgeWeight 的 Edge 是否已经存在于 BST 中（也比较 srcNode 和 destNode），如果找到，则将其丢弃，否则将其添加到 BST。通过这种方式，您将在 BST 中拥有所有独特的边缘。

在 BST 中搜索只需要 log(n) 时间（n=BST 中的元素数）。如果边数为“m”，则复杂度为 m log(n)

PS：我假设从 srcNode '1' 到 destNode '2' 将有具有相同 edgeWeight 的重复边。如果您在两个节点上有多个具有不同 edgeWeight 的边，那么您可以选择最小的一个并在 BST 中替换它，同时插入（如果它已经存在）。这样，您将拥有该 Edge 的最低 edgeWeight

于 2013-08-21T19:32:20.677 回答
0

就像@zapl 所说，你可以使用Set.

无论如何，您必须对边缘进行排序，为什么不考虑实现compareTo，然后对边缘进行排序，然后如果一个边缘等于前一个边缘，则跳过它。

见：http ://www.mkyong.com/java/java-object-sorting-example-comparable-and-comparator/

顺便说一句，Krushkal 不要求边缘是唯一的，第二次处理边缘时， fa[u] 将等于 fa[v] 并且该边缘将被忽略。

于 2013-08-21T18:42:09.310 回答