普里姆最小生成树算法

// Prim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
const int GraphSize=10;
const int INFINITY=65535;
class MGraph
{
public:
MGraph(){};
~MGraph(){};
bool CreateGraph(int **pGraph,int iSize);
void PrimTree();
int getVertexNum(){return m_vertexNum;}
private:
int m_vertexs[GraphSize];
int m_edges[GraphSize][GraphSize];
int m_vertexNum;
};
bool MGraph::CreateGraph(int **pGraph, int iSize)
{
if(iSize>GraphSize)
return false;
m_vertexNum=iSize;
for(int i=0;i<iSize;i++)
m_vertexs[i]=i;
for(int j=0;j<iSize;j++)
{
for(int k=0;k<iSize;k++)
{
m_edges[j][k]=*((int*)pGraph+iSize*j+k);
}
}
//输出创建的图
cout<<" ";
for(int i=0;i<iSize;i++)
cout<<" "<<i<<" ";
cout<<endl;
for(int i=0;i<iSize;i++)
{
cout<<i<<" ";
for(int j=0;j<iSize;j++)
{
cout<<m_edges[i][j]<<" ";
}
cout<<endl;
}

return true;
}
void MGraph::PrimTree()
{
int adjvex[GraphSize];//保存相关连的顶点的下标
int lowcost[GraphSize];//保存与顶点相连的权值最小的边的权值
int min,i,j,k;
lowcost[0]=0;//V0作为最小生成树的根开始，进行遍历
adjvex[0]=0;
for(i=1;i<m_vertexNum;i++)
{
lowcost[i]=m_edges[0][i];// 将邻接矩阵第0行所有权值先加入数组
adjvex[i]=0;// 初始化全部先为V0的下标
}
for(i=1;i<m_vertexNum;i++)
{
min=INFINITY;
k=0;
j=1;
while(j<m_vertexNum)
{
//找出lowcost中存储的边的最小权值
if(lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];
k=j;//保存找到的最小权值的下标
}
j++;
}
//输出权值最小的边
cout<<"("<<adjvex[k]<<","<<k<<")"<<endl;
lowcost[k]=0;//将考察完的点的权值设置为0
//由于加入了新的点，所以需要更新lowcost数组
for(j=1;j<m_vertexNum;j++)
{
if(lowcost[j]!=0 && m_edges[k][j]<lowcost[j])
{
//更新与顶点j相连接的最短边的权值
lowcost[j]=m_edges[k][j];
//更新关联顶点的下标
adjvex[j]=k;
}
}
}

}
int _tmain(int argc, _TCHAR* argv[])
{
MGraph graph;
int edge[9][9]={0,71,16,99,60,
71,0,72,12,44,
16,72,0,65,42,
99,12,65,0,50,
60,44,42,50,0
};
graph.CreateGraph((int **)edge,5);
graph.PrimTree();
system("pause");
return 0;
}