Boruvka MSTアルゴリズムを使用してフォレスト内のエッジを検索する最善の方法は何ですか？

Question

現在、Baruvkaのアルゴリズムを以下のようにコーディングしています。しかし、すでに欲張りの選択肢を使ってすでに撮影されているエッジのリストにすでに存在する場合、エッジe = uvをチェックする質問が与えられます。 O（logn）時間内にエッジeを検索するにはどうすればよいですか？これを手伝ってください... BFSまたはDFSを使用して検索操作を実行し、エッジが存在するかどうかを確認できますが、すべてのフェーズでそれを行うとコストがかかる操作になります。

Boruvka 
{ 
while (T < n-1 edges) 
{ 
Find the components of T 
for each tree Ti of the forest T 
{ 
Find the smallest weight edge e = uv such that u is in Ti and v is not in Ti 

//Before adding e to T I have to check if it already exists in the list of greedy edges or not. If it exists then I would like to skip adding e to T and go to the next phase. 
Add e to T 
} 
} 
return T 
} 

しかし、1つのエッジを複数回追加するという問題があります。そのためには、エッジを追加する前にエッジが既にTに追加されているかどうかを確認する必要があります。このチェックにO（n）実装がありますか？

Answer 1

各コンポーネントに個別のデータ構造またはその他のデータ構造を使用する必要があります。エッジが2つの異なる接続コンポーネントを接続している場合、ツリーエッジリストにはどのようにエッジが存在していますか？ Boruvka's algorithmをお読みください。

エッジを選択すると、そのエッジで接続されている2つのコンポーネントをマージする必要があります。マージするときには、この大きなコンポーネントを新しい頂点と見なしてください。新しい頂点は、外側に行く構成コンポーネントのエッジである必要があります。