prim.txt

Prim最小生成树Prim最小生成树Prim最小生成树

#include<iostream>

using namespace std;

#define csMaxLimit 101
#define csINF 999999999

int iNumOfNodes;
int iCost[csMaxLimit][csMaxLimit];
bool bNodeFromFlag[csMaxLimit],bNodeToFlag[csMaxLimit];
int iNodeFromCount;
int iTotalCost;

struct stMinCostEdgeInfo
{
	int iFromNode;
	int iToNode;
	int iWeight;
};

void procInput()
{
	int i,j;

	for(i=1;i<=iNumOfNodes;i++)
	{
		for(j=1;j<=iNumOfNodes;j++)
		{
			scanf("%d",&iCost[i][j]);
		}
	}
}

void procInitial()
{
	int i,iStartNode;

	for(i=1;i<=iNumOfNodes;i++)
	{
		bNodeFromFlag[i]=false;
		bNodeToFlag[i]=true;
	}

	iTotalCost=0;
	iStartNode=1;
	iNodeFromCount=1;
	bNodeFromFlag[iStartNode]=true;
	bNodeToFlag[iStartNode]=false;
}

void procOuput()
{
	printf("%d\n",iTotalCost);
}

struct stMinCostEdgeInfo FunGetMinCost()
{
	int i,j,iTempMin,iFromIndex,iToIndex;
	struct stMinCostEdgeInfo stRetValue;

	iTempMin=csINF;
	iFromIndex=0;
	iToIndex=0;
	for(i=1;i<=iNumOfNodes;i++)
	{
		if(bNodeFromFlag[i])
		{
			for(j=1;j<=iNumOfNodes;j++)
			{
				if(bNodeToFlag[j])
				{
					if(iCost[i][j]<iTempMin)
					{
						iFromIndex=i;
						iToIndex=j;
						iTempMin=iCost[i][j];
					}
				}
			}
		}
	}
	stRetValue.iWeight=iTempMin;
	stRetValue.iFromNode=iFromIndex;
	stRetValue.iToNode=iToIndex;

	return stRetValue;
}

void procPrim()
{
	struct stMinCostEdgeInfo stMinCostEdge;

	while(iNodeFromCount<iNumOfNodes)
	{
		stMinCostEdge=FunGetMinCost();
		iTotalCost+=stMinCostEdge.iWeight;
		bNodeFromFlag[stMinCostEdge.iToNode]=true;
		bNodeToFlag[stMinCostEdge.iToNode]=false;
		iNodeFromCount++;
	}
}

int main()
{
	while (1==scanf("%d",&iNumOfNodes))
	{
		procInput();
		procInitial();
		if(iNumOfNodes>1)
		{
			procPrim();
		}
		procOuput();
	}

	return 0;
}