java - 複雑な構造から重複を除去するための効率的なアルゴリズム - MST の Krushkal のアルゴリズムの一部

Question

ArrayList<Edge>重複した値を削除する必要があります 。Edgeクラスは次のとおりです

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

Krushkal のアルゴリズムを実装するために、グラフの最小全域木を計算したいと考えています。それを計算するには、リストからすべての重複を削除する必要があります。したがって、srcNode、destNode、および edgeWeight を使用して、この種のデータ構造から重複する値を削除するのに最適なアルゴリズムはどれでしょうか。Edge

Answer 1

@zaplが言ったように、使用できますSet。

とにかく、エッジをソートする必要があります。実装を検討してから、エッジをソートしてから、compareTo1 つのエッジが前のエッジと等しい場合はスキップしてください。

参照: http://www.mkyong.com/java/java-object-sorting-example-comparable-and-comparator/

ところで、Krushkal ではエッジが一意である必要はありません。エッジが 2 回目に処理されると、fa[u] は fa[v] に等しくなり、このエッジは無視されます。