用於創建圖形的邏輯C++

我正在研究一個項目，其中給出了A或B權重的邊的列表。我最終需要確定是否可以創建具有'x'個數的生成樹一個邊緣。用於創建圖形的邏輯C++

現在我正在嘗試製作所有用於創建最小生成樹的邊的列表，並通過製作我已使用的頂點列表來做到這一點。如果兩個頂點已被使用，那麼該邊被丟棄。我遇到的問題是，一旦我完成我的圖形，我通常會留下兩半圖形，因爲連接兩半的邊緣已經被使用，所以這些圖形沒有連接。有關我如何解決這個問題的任何想法，還是總體方法錯誤？

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; 
    }

來源

2016-11-25 hournet562

只需使用Kruskal的算法使用的標準：添加邊緣到圖形，如果它不形成環路。要檢查這一點，你必須檢查兩個事件節點是否連接到相同的連接組件。這可以通過Union-Find數據結構高效地完成。即無論何時添加邊，都要統一兩個頂點的組成部分。在添加邊緣之前，檢查兩個組件是否相同。

來源

2016-11-25 02:49:31

用於創建圖形的邏輯C++

回答

相關問題