主函數(shù)
int?main(void)
{
	CMap?*pMap=new?CMap(6);
	
	Node?*pNodeA=new?Node('A');
	Node?*pNodeB=new?Node('B');
	Node?*pNodeC=new?Node('C');
	Node?*pNodeD=new?Node('D');
	Node?*pNodeE=new?Node('E');
	Node?*pNodeF=new?Node('F');

	
	pMap->addNode(pNodeA);
	pMap->addNode(pNodeB);
	pMap->addNode(pNodeC);
	pMap->addNode(pNodeD);
	pMap->addNode(pNodeE);
	pMap->addNode(pNodeF);

	
	
	pMap->setValueToMatrixForUndirectedGraph(0,1,6);
	pMap->setValueToMatrixForUndirectedGraph(0,4,5);
	pMap->setValueToMatrixForUndirectedGraph(0,5,1);
	pMap->setValueToMatrixForUndirectedGraph(1,2,3);
	pMap->setValueToMatrixForUndirectedGraph(1,5,2);
	pMap->setValueToMatrixForUndirectedGraph(2,5,8);
	pMap->setValueToMatrixForUndirectedGraph(2,3,7);
	pMap->setValueToMatrixForUndirectedGraph(3,5,4);
	pMap->setValueToMatrixForUndirectedGraph(3,4,2);
	pMap->setValueToMatrixForUndirectedGraph(4,5,9);
	
	pMap->primTree(0);


	system("pause");
	return?0;
}

普利姆算法

void?CMap::primTree(int?nodeIndex)//普利姆生成樹
{
	int?value=0;//邊的權(quán)值保存到value中?
	int?edgeCount=0;//取出的邊數(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)//邊數(shù)小于m_iCapacity-1則一直要循環(huán)?
	{
		int?temp=?nodeVec.back();//取出nodeIndex，back()函數(shù)是取當(dāng)前數(shù)組中尾部的元素
		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);
				}
			}
		}//所有邊放入備選邊集合中
		
		//從可選邊集合中找出最小的邊?
		int?edgeIndex=getMinEdge(edgeVec);//找最小權(quán)值邊的索引?
		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++;
		
		//nodeVec為點集合?
		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;//初始化最小權(quán)值?
	int?edgeIndex=0;
	int?i=0;
	for(i=0;i<edgeVec.size();i++)
	{
		if(!edgeVec[i].m_bSelected)
		{
			minWeight=edgeVec[i].m_iWeightValue;
			edgeIndex=i;
			break;//這里需要注意?
		}
	}
	
	if(minWeight==0)
	{
		return?-1;
	}
	//判斷后面是否還存在最小權(quán)值邊?
	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;
}