Логика для создания графика C++

Question

Я работаю над проектом, где мне задан список ребер с весом A или B. Мне нужно в конце концов определить, можно ли создать остовное дерево с 'x' числом Края.

Сейчас я пытаюсь составить список всех ребер, которые используются при создании минимально охватывающего дерева, и делаю это, создав список вершин, которые я использовал. Если две из вершин были использованы, то эти ребра отбрасываются. Проблема, с которой я столкнулась, заключается в том, что, как только я дойду до конца своего графика, я часто оставляю две половинки графиков, которые не связаны, потому что край, который соединял бы две половины, уже использовался. Любые мысли о том, как я могу исправить эту проблему, или общий подход неправильный?

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

Просто используйте критерий, который использует алгоритм Крускала: Добавить ребро в графе, если она не образует петлю. Чтобы проверить это, вы должны проверить, подключены ли два инцидентных узла к одному и тому же подключенному компоненту. Это можно сделать эффективно с помощью структуры данных Union-Find. То есть всякий раз, когда вы добавляете ребро, объедините компоненты обеих вершин. Перед добавлением ребра проверьте, совпадают ли эти два компонента.