博客

用Prim算法构造最小生成树

1. 问题
举一个实例，画出采用Prim算法构造最小生成树的过程，并按实验报告模板编写算法。
2. 解析
假设N=(V，{E})是连通网，TE为最小生成树中边的集合。
1)初始U={u0}(u属于V)，TE=P；
2)在所有u属于U，v属于V-U的边中选一条代价最小的边(uo，v0)并入集合TE，同时将v0并入U；
3)重复2)，直到U=V为止。
此时，TE中必含有n-1条边，则T=(V，{TE})为N的最小生成树。

每个顶点i有两个标记值:
顶点i离U集合里的那个顶点最近，这个最近顶点记作u
边（u，i）的权值

1. 如下图，目前只有V0在U集合中，选择最小权值1的V2进入U
2. 如下图，现在V0,V2在集合U中，V1,V4,V5的最小权值均有变化，选择最小权值V5进入集合
   
3. 如下图，现在V0,V2,V5在集合U中，V3的最小权值有变化，选择最小权值V3进入集合
   
4. 如下图，现在V0,V2,V5,V3在集合U中，权值无变化，选择最小权值V1进入集合
   
5. 如下图，现在V0,V2,V5,V3,V1在集合U中，V4权值变化，选择最小权值V4进入集合
   则可以得到最小生成树为（0，2）（2，5）（5，3）（2，1）（1，4）
   
   3. 设计

int Minium(vexValue a[],int n){//查找函数 
	//找V-U集合中的最小值顶点
	int k = -1;
	int min =INF;
	for(int i=0;i<n;i++){
		if(a[i].weigth != 0 && a[i].weigth < min)
		{
			min=a[i].weigth;
			k=i;
		}
	}
	return k;//返回权值最小的顶点的编号 
}
void minSpanTree_prim(AdjGraph &g,int u0)
{//g是用邻接表作为存储结构的图 ，u0是选定的初始顶点 
	vexValue *closedge = new vexValue[g.n];
	//定义一个辅助数组，用于对每个顶点做标记 
	closedge[u0].u=0;// 初始的时候，u集合里只有初始顶点，所以初始顶点的u的值是0 
	closedge[u0].weigth=0;//权值也标为0 
	for(int i=0;i<g.n;i++){
		if(i != u0){
			closedge[i].u=u0;//初始化 ，对于每个顶点的离u集合最近的顶点 都标记为初始顶点 
			closedge[i].weigth=INF;	//权值标记为无穷大	
		}
	}
	arcNode*p=g.adjlist[u0].firstArc;//用u0去遍历链表，找初始顶点的能够直接到达的权值去做修改 
	while(p){//p指向第一个顶点 
		closedge[p->adj].weigth = p->weigth;
		//对链表遍历 ，对u0的邻接点的权值用边上的权值修改 
		p = p->nextarc;
	}
	for(int i=0;i<g.n - 1;i++){
		int k=Minium(closedge,g.n);
		//顶点里选标记值最小的顶点 
		cout<<"("<<closedge[k].u<<","<<k<<")"<<endl;
		closedge[k].weigth = 0;
		//顶点k已经加入集合，去修改其他顶点的标记，即遍历邻接链表k 
		arcNode *p=g.adjlist[k].firstArc;
		while(p){
			if(p->weigth < closedge[p->adj].weigth){
				closedge[p->adj].u = k;
				closedge[p->adj].weigth = p->weigth;
			}
			p=p->nextarc;
		} 
	}
	delete []closedge;//把辅助数组所在的空间释放 
}