グラフを作成するためのロジック

Question

私はAまたはBの重みを持つエッジのリストが与えられているプロジェクトに取り組んでいます。最終的に 'x'の数でスパニングツリーを作成できるかどうかを判断する必要がありますAエッジ。

今、最小スパニングツリーの作成に使用されているすべてのエッジのリストを作成しようとしています。これは、使用した頂点のリストを作成することによって行います。 2つの頂点が使用された場合、その辺は破棄されます。私が抱えている問題は、一度グラフの終わりに達すると、2つの半分を結ぶエッジがすでに使用されているため、接続されていないグラフが2つ半分残っていることが多いことです。どのように私はこの問題を解決することができますか、または全体的なアプローチが間違っている任意の考えですか？

struct Edge{ 
    int start; 
    int end; 
    char letter; 
    bool used; 

}; 

void PrimWhite(...) 
{ 
vector<int> usedVertices; 
int count,maxNum,begin,end; 

int totalVertexs = 0; 
maxNum = whiteEdge.size(); 

Edge temp; 
Edge *point = &temp; 
Edge *usedorNah; 

for (count = 0;count < maxNum; count++) 
{ 
    temp = whiteEdge[count]; 
    usedorNah = &whiteEdge[count]; 
    begin = point->start; 
    end = point->end; 

    if ((find(usedVertices.begin(), usedVertices.end(), begin) == usedVertices.end()) && (find(usedVertices.begin(), usedVertices.end(), end) == usedVertices.end())) 
    { 
     usedVertices.push_back(begin); 
     usedVertices.push_back(end); 
     totalVertexs = totalVertexs + 2; 
     usedorNah->used = true; 
    } 
    else if ((find(usedVertices.begin(), usedVertices.end(), begin) == usedVertices.end()) && (find(usedVertices.begin(), usedVertices.end(), end) != usedVertices.end())) 
    { 
     usedVertices.push_back(begin); 
     totalVertexs++; 
     usedorNah->used = true; 
    } 
    else if ((find(usedVertices.begin(), usedVertices.end(), begin) != usedVertices.end()) && (find(usedVertices.begin(), usedVertices.end(), end) == usedVertices.end())) 
    { 
     usedVertices.push_back(end); 
     totalVertexs++; 
     usedorNah->used = true; 
    } 

Answer 1

ただ、クラスカルのアルゴリズムが使用する基準を使用します。それがループを形成しない場合は、グラフにエッジを追加します。これを確認するには、2つのインシデントノードが同じ接続コンポーネントに接続されているかどうかを確認する必要があります。これは、Union-Findデータ構造を使用して効率的に行うことができます。私。エッジを追加するたびに、両方の頂点のコンポーネントを結合します。エッジを追加する前に、2つのコンポーネントが同じかどうかを確認してください。