基本的に、頂点 u と v が同じコンポーネントにないかどうかを確認する以外に、もう 1 つの条件を追加して、クラスカルのアルゴリズムを変更しようとしています。ユニオン検索データ構造がどのように機能するかを漠然と理解しているので、実際に正しい考えを持っているかどうかを確認したかった.
無向グラフ G = (V, E) と、V のいくつかの頂点 (頂点 A ⊂ V のサブセット) を含む集合 A があるとすると、V の頂点 u ごとに (ループ) 、u もこのセット A に含まれています。
(Full Kruskal's algorithm omitted)
original_comp = make_sets(V)
A_comp = make_sets(A)
for each edge (u, v) in E:
if (find(original_comp, u) == find(A_comp, u)):
// do something
設定されたパラメーターが異なる (つまりラベルが異なる) ため、これは機能しませんか? 確認したかっただけなのに…
明確にするために、エッジ (u, v) にセット A の頂点の 1 つが含まれているかどうかを知る必要があります。そして、これを達成するために Union-Find を使用しようとしていました (find() には O(1) 時間がかかるため)。セット A をトラバースして各要素を比較する代わりに...これが可能かどうか誰か教えてもらえますか? それとも、配列トラバーサル メソッドを使用する必要がありますか?
ありがとうございました。