//普利姆算法
void CMap::primTree(int nodeIndex) {
vector<int> nodeVec;
vector<Edge> edgeVec;
int value = 0;
int edgeCount = 0;
nodeVec.push_back(nodeIndex);
cout << m_pNodeArray[nodeIndex].m_cData << endl;
m_pNodeArray[nodeIndex].m_bIsVisited = true;
while (edgeCount < m_iCapacity - 1) {
int temp = nodeVec.back();
for (int i = 0; i < m_iCapacity; ++i) {
getValueFromMatrix(temp, i, value);
if (value != 0) {
if (m_pNodeArray[i].m_bIsVisited) {
continue;
} else {
Edge edge(value, temp, i);
edgeVec.push_back(edge);
}
} else {
continue;
}
}
int min = getMinEdge(edgeVec);
edgeVec[min].m_bIsSelect = true;
m_pEdgeArray[edgeCount] = edgeVec[min];
edgeCount++;
cout << edgeVec[min].m_iNodeIndexA << "---"
<< edgeVec[min].m_iNodeIndexB << " ";
cout << edgeVec[min].m_iWeightValue << endl;
int bNodeIndex = edgeVec[min].m_iNodeIndexB;
nodeVec.push_back(bNodeIndex);
m_pNodeArray[bNodeIndex].m_bIsVisited = true;
cout << m_pNodeArray[bNodeIndex].m_cData << endl;
}
}
int CMap::getMinEdge(vector<Edge> vec) {
int edgeIndex = 0;
int minWeight = 0;
int i = 0;
for (; i < vec.size(); ++i) {
if (!vec[i].m_bIsSelect) {
edgeIndex = i;
minWeight = vec[i].m_iWeightValue;
break;
}
}
if (minWeight == 0) {
return -1;
}
for (; i < vec.size(); ++i) {
if (vec[i].m_bIsSelect) {
continue;
} else {
if (minWeight > vec[i].m_iWeightValue) {
minWeight = vec[i].m_iWeightValue;
edgeIndex = i;
}
}
}
return edgeIndex;
}
这是代码,检查了好多遍,完全照着写打印结果也是错的。
下面的输出:
A
0---5 1
F
5---1 2
B
5---3 2
D
1---2 3
C
3---4 4
E
求大佬解答。。