请问数据结构之探险篇
请问一下有没有数据结构之探险篇的克鲁斯卡尔求最小生成树的源代码?
小俊199641
2018-04-26
1 回答
void CMap::kruskalTree()
{
int value = 0;
int edgeCount = 0;
vector<vector<int>> nodeSets;
//之前一直显示vector subscript out of range，这是因为后面出现对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.找出算法结束条件
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根据点所在的集合的不同做出不同的处理
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;
}
}
举报
0/150
提交
取消
