請問數(shù)據(jù)結(jié)構(gòu)之探險篇
請問一下有沒有數(shù)據(jù)結(jié)構(gòu)之探險篇的克魯斯卡爾求最小生成樹的源代碼?
小俊199641
2018-04-26
1 回答
舉報
0/150
提交
取消
2018-04-30
void CMap::kruskalTree()
{
int value = 0;
int edgeCount = 0;
vector<vector<int>> nodeSets;
//之前一直顯示vector subscript out of range，這是因為后面出現(xiàn)對vector直接取vec[]的語句，這是不對的
//因為vector沒有分配空間，我在這里分配空間后就可以了。
nodeSets.resize(m_iCapacity*m_iCapacity);
vector<Edge>edgeVec;
for (int i = 0; i < m_iCapacity; i++)
{
for (int k = i+1; k < m_iCapacity; k++)
{
getValueFromMatrix(i, k, value);
if (value != 0)
{
Edge edge(i,k, value);
edgeVec.push_back(edge);
}
}
}
//1.找出算法結(jié)束條件
while (edgeCount < m_iCapacity -1)
{
//2從邊集合中找出最小邊
int minEdgeIndex = getMinEdge(edgeVec);
edgeVec[minEdgeIndex].m_bSelected = true;
//3找出連接最小邊的點
int nodeAIndex = edgeVec[minEdgeIndex].m_iNodeIndexA;
int nodeBIndex = edgeVec[minEdgeIndex].m_iNodeIndexB;
//4找出點所在的點的集合
bool nodeAIsInSet = false;
bool nodeBIsInSet = false;
int nodeAInSetLabel = -1;
int nodeBInSetLabel = -1;
for (int i = 0; i < (int)nodeSets.size(); i++)
{
nodeAIsInSet = IsInset(nodeSets[i], nodeAIndex);
if (nodeAIsInSet)//點在指定的集合中
{
nodeAInSetLabel = i;//A點所在的點集合的索引
}
}
for (int i = 0; i < (int)nodeSets.size(); i++)
{
nodeBIsInSet = IsInset(nodeSets[i], nodeBIndex);
if (nodeBIsInSet)//點在指定的集合中
{
nodeBInSetLabel = i;//A點所在的點集合的索引
}
}
//5根據(jù)點所在的集合的不同做出不同的處理
if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
{
vector<int>vec;
vec.push_back(nodeAIndex);
vec.push_back(nodeBIndex);
nodeSets.push_back(vec);
}
else
if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1)//A不在任何集合中
{
nodeSets[nodeBIndex].push_back(nodeAIndex);
}
else
if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
{
nodeSets[nodeAIndex].push_back(nodeBIndex);
}
else
if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)
{
mergeNodeSet(nodeSets[nodeAIndex], nodeSets[nodeBIndex]);//把B合并到A當中，B銷毀
for (int k = nodeBInSetLabel; k < (int)nodeSets.size()-1; k++)
{
nodeSets[k] = nodeSets[k + 1];
}
}
else
if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel)
{
continue;
}
m_pEdge[edgeCount] = edgeVec[minEdgeIndex];//保存邊
edgeCount++;
cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "-------------" << edgeVec[minEdgeIndex].m_iNodeIndexB << "? ?";
cout << edgeVec[minEdgeIndex].m_iWeightValue << endl;
}
}