只输出一个A
void Map::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++)
{
getValueFromMatirx(temp,i,value);
if(value!=0)
{
if(m_pNodeArray[i].m_bIsVisited)
continue;
else
{
Edge edge(temp,i,value);
edgeVec.push_back(edge);
}
}
}
//从备选边集合找出最小的边
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[nodeIndex];
edgeCount++;
int nextNodeIndex=edgeVec[nodeIndex].m_iNodeIndexB;
nodeVec.push_back(nextNodeIndex);
m_pNodeArray[nextNodeIndex].m_bIsVisited=true;
cout<<m_pNodeArray[nextNodeIndex].m_cdata<<endl; //打印点
}
}
int Map::getMinEdge(vector<Edge> edgeVec)
{
int minWeight=0;
int edgeIndex=0;
int i=0;
for(;i<(int)edgeVec.size();i++)
{
if(!edgeVec[i].m_bSelected)
{
minWeight=edgeVec[i].m_iWeightValue;
edgeIndex=i;
break;
}
}
if(minWeight==0)
{
return -1;
}
for(;i<(int)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;
}
int main()
{
Map *pmap=new Map(6);
Node *pnode1=new Node('A');
Node *pnode2=new Node('B');
Node *pnode3=new Node('C');
Node *pnode4=new Node('D');
Node *pnode5=new Node('E');
Node *pnode6=new Node('F');
pmap->addNode(pnode1);
pmap->addNode(pnode2);
pmap->addNode(pnode3);
pmap->addNode(pnode4);
pmap->addNode(pnode5);
pmap->addNode(pnode6);
pmap->setValueMatirxForUndirectGraph(0,1,6); //设置无向连接矩阵
pmap->setValueMatirxForUndirectGraph(0,4,5);
pmap->setValueMatirxForUndirectGraph(0,5,1);
pmap->setValueMatirxForUndirectGraph(1,2,3);
pmap->setValueMatirxForUndirectGraph(1,5,2);
pmap->setValueMatirxForUndirectGraph(2,5,8);
pmap->setValueMatirxForUndirectGraph(2,3,7);
pmap->setValueMatirxForUndirectGraph(3,5,4);
pmap->setValueMatirxForUndirectGraph(3,4,2);
pmap->setValueMatirxForUndirectGraph(4,5,9);
pmap->primTree(0);
// pmap->printMatirx();
//
// cout<<endl;
// pmap->resetNode();
// pmap->depthFirstTravel(0);
//
// cout<<endl;
// pmap->resetNode();
// pmap->breadthFirstTravel(0);
return 0;
}
