c++ - 创建图c++的逻辑

Question

我正在做一个项目，在该项目中，我获得了权重为 A 或 B 的边列表。我最终需要确定是否可以创建具有“x”个 A 边的生成树。

现在我正在尝试列出用于创建最小生成树的所有边，并通过列出我使用过的顶点来做到这一点。如果使用了两个顶点，则丢弃该边。我遇到的问题是，一旦我到达我的图表的末尾，我经常会留下两半没有连接的图表，因为已经使用了连接两半的边。关于如何解决此问题的任何想法，或者整体方法是否错误？

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

只需使用 Kruskal 算法使用的标准:如果不形成环，则向图中添加一条边。要检查这一点，您必须检查两个事件节点是否连接到同一个连接组件。这可以通过 Union-Find 数据结构有效地完成。 IE。每当你添加一条边时，将两个顶点的组件 union 起来。在添加边之前，检查两个组件是否相同。