void Map::primTree(int nodeIndex)

{

? ? int value=0;

? ? int edgeCount=0;? ?//邊計(jì)數(shù)器

? ? 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)? ?//算法結(jié)束條件

? ? {

? ? ? ? int temp=nodeVec.back();

? ? ? ? //找出所有備選邊，進(jìn)數(shù)組

? ? ? ? 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;? //打印點(diǎn)

? ? }

}

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);? ? ?//設(shè)置無向連接矩陣

? ? 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;

}