编辑代码

#include <iostream>
using namespace std;
#define INF 65535
#define MAX 10
/*定义图结构体*/
typedef struct
{
	char Vertex[MAX];		//顶点数组
	int arc[MAX][MAX];		//邻接表
	int numVertex, numEdges;	//顶点数，边数
}MGraph;

/*图的初始化，顶点数，邻接矩阵*/
void GraphIint(MGraph *G)
{
	int i, j;
	cout<<"input numVertex less than "<<MAX<<endl;
    cin>>G->numVertex;		//初始化顶点数 
	/*初始化邻接矩阵*/
	for(i = 0; i < G->numVertex; i++)
	{
		for(j = i; j < G->numVertex; j++)
		{
			 cout<<"arc["<<i<<']'<<'['<<j<<']'<<endl;
             cin>>G->arc[i][j];
			 G->arc[j][i] = G->arc[i][j];		//对称阵 
		}
		cout<<endl;
	}
	/*调试输出用*/
	for(i = 0; i < G->numVertex; i++)
	{
		for(j = 0; j < G->numVertex; j++)
		{
			cout<<"  "<<G->arc[i][j];
		}
		cout<<endl;
	}
	/*调试输出用*/
	
}
/*普里姆算法最小生成树*/
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;		//min保存当前最短路径的边的权值，k保存当前最短路径的顶点编号 
	int lowcost[MAX];		//保存相关边的权值 
	int adjvex[MAX];		//保存相关顶点的权值 
	
	/*初始化lowcost和adjvex*/
	lowcost[0] = 0;			//初始化lowcost的第一个值	
	adjvex[0] = 0;			//初始化adjvex的第一个值
	/*初始化lowcost，adjvex的剩下的值*/	
	for(i = 1; i < G.numVertex; i++)
	{
		lowcost[i] = G.arc[0][i];		//初始化lowcost为V0顶点的相关边权值（v0的行权值） 
		adjvex[i] = 0;					 
	}
	/*Prim真正核心*/
	for(i = 1; i < G.numVertex; i++)
	{
		min = INF;					//初始化min，保证每次都从连通的路径开始搜索 
		k = 0;						//从第一个顶点开始搜索 
		j = 1;						//第一个顶点已经被认为是最小生成树的节点，无需从0开始 
		/*搜索当前lowcost数组的最小值，保存这个最小值的编号*/
		while(j < G.numVertex)
		{
			if((lowcost[j] != 0) && (lowcost[j] < min))		//lowcost为0，表示该列已经搜索，逐行搜索时不再 
			{												//搜索lowcost中位于这一列的元素  
				min = lowcost[j];
				k = j;				//保存最小值的编号 	
			}				
			j++;
		}
		/*打印路径边 */
		cout<<'('<<adjvex[k]<<','<<k<<')'<<endl;
		/*将已经找到的最小生成树的边置0，下次搜索时不再继续搜索该边 */	
		lowcost[k] = 0;						
		/*更新lowcost数组*/
		for(j =1; j < G.numVertex; j++)
		{
			/*比较lowcost和被筛选出的顶点的边（行权值），取较小值，保存在lowcost中*/
			if((lowcost[j] != 0) && (G.arc[k][j] < lowcost[j]))
			{
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;				//标记k为最小生成树的顶点 
			}
		}
	}	
} 

int main(void)
{
	MGraph G = {0};				//创建图 
	GraphIint(&G);				//图的初始化 
	MiniSpanTree_Prim(G);		//普里姆最小生成树 
	return 0;
}