普利姆算法的输出有问题,麻烦大家看看是哪里错了,谢谢!
void CMap::primTree(int nodeIndex)
{
int value=0;
int edgeCount=0;
vector<int> nodeVec;
vector<Edge> edgeVec;//备选边的集合
cout<<m_pNodeArray[nodeIndex].m_cData<<endl;
nodeVec.push_back(nodeIndex);
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(temp,i,value);
edgeVec.push_back(edge);
}
}
} //for循环做完就将与temp相关的所有边放进edgeVec中
//从可选边集合中找出最小的边
int edgeIndex = getMinEdge(edgeVec);
edgeVec[edgeIndex].m_bSelected = true;
cout<<edgeVec[edgeIndex].m_iNodeIndexA<<"--"<<edgeVec[edgeIndex].m_iNodeIndexB<<" ";
cout<<edgeVec[edgeIndex].m_iWeightValue<<endl;
m_pEdge[edgeCount] = edgeVec[edgeIndex];
edgeCount++;
int nextNodeIndex = edgeVec[edgeIndex].m_iNodeIndexB;
nodeVec.push_back(nextNodeIndex);
m_pNodeArray[nextNodeIndex].m_bIsVisited=true;
cout<<m_pNodeArray[nextNodeIndex].m_cData<<endl;
}
}
int CMap::getMinEdge(vector<Edge>edgeVec)
{
int minWeight=0;
int edgeIndex=0;
int i=0;
for(;i<edgeVec.size();i++)
{
if(!edgeVec[i].m_bSelected)
{
minWeight = edgeVec[i].m_iWeightValue;
edgeIndex =i;
break;
}
}
if(minWeight==0)//当前edgeVec中的所有边已经被访问
{
return -1;
}
for(;i<edgeVec.size();i++)
{
if(edgeVec[i].m_bSelected)
{
continue;
}
else
{
if(minWeight>edgeVec[i].m_iWeightValue)
{
minWeight=edgeVec[i].m_iWeightValue;
edgeIndex = i;
}
}
}
return edgeIndex;
}