博客

题目概述

输入任意的一个网，用prime算法构造最小生成树

算法分析

取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 条边为止。

源代码

/*
*******************************************************************
20.输入任意的一个网，用prime算法和Krustal算法（选做）构造最小生成树
******************************************************************* 
摘要： 
无向网的存储结构 ：邻接矩阵法
*/
#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50  //结点个数的最大值 
#define MaxInt 32767  //定义无穷大 
#define MaxEdgeNum 50 //边的最大值 
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
	VertexType vexs[MaxVexNum];//顶点表 
	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
	int vexnum,edgenum;//顶点数，边数 
}AMGraph; 

//用邻接表法建立网的存储结构 
void createGraph(AMGraph &g){
	printf("请输入顶点数：\n");
	scanf("%d",&g.vexnum);
	printf("请输入边数：\n");
	scanf("%d",&g.edgenum);
	
	//初始化顶点表 
	for(int i=0;i<g.vexnum;i++){
		g.vexs[i]=i; //初始化顶点标号 
	} 
	for(int i=0;i<g.vexnum;i++){
		for(int j=0;j<g.vexnum;j++){
			g.arcs[i][j]=MaxInt;//初始化边的权重 
			if(i==j) g.arcs[i][j]=0;
		}
	} 
	printf("请输入三元组[x,y,w]\n");
	for(int i=0;i<g.edgenum;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g.arcs[x][y]=w;
		g.arcs[y][x]=w;
	}
}
 
//普利姆算法
//集合U表示已经加入生成树中顶点的集合 
 struct Node    //需要用一个结构体来记录产生的最小的生成树 
{  
    int adjvex;//最小边在U的那个顶点     
    int lowcost;//最小边上的权值    
}MinTree[MaxVexNum]; 
 
void Prim(AMGraph g,int k){//从u结点（标号为k)出发，寻找MST 
	//初始化closedge
	printf("最小路径：\n");
	int n=g.vexnum;
	int i;
	for(i=0;i<n;i++){
		if(i!=k){//不考虑结点与自身之间的路径 
			MinTree[i].adjvex=k;
			MinTree[i].lowcost=g.arcs[i][k];	
		} 
	} 
	MinTree[k].lowcost=0;//初始，U={u};
	int min,u0,v0,sum=0; 
	for(int i=0;i<n-1;i++){//添加n-1条边 
		min=MaxInt;
		for(int j=0;j<n;j++){ 
		 	if(MinTree[j].lowcost>0){//尚未落在生成树上的顶点集 
		 		if(MinTree[j].lowcost<min){ //寻找最小权值的边 
		 			k=j;
		 			min=MinTree[j].lowcost;
				}
			}
		}
	 	u0=MinTree[k].adjvex;
		sum+= MinTree[k].lowcost;
	 	printf("[%d,%d]\n",u0,k);
	 	MinTree[k].lowcost=0;
	 	for(int j=0;j<n;j++){//更新未被加入生成树的顶点的lowcost 
	 		if(g.arcs[k][j]<MinTree[j].lowcost){
	 		MinTree[j].lowcost=g.arcs[k][j];
	 		MinTree[j].adjvex=g.vexs[k]; 
		 	} 
	 	}	  	
	}
	printf("最小路径长度为：%d\n",sum);
}
 
//Kruskal算法

//寻找根节点的函数 
int GetRoot(int v[],int p){
	while(p!=v[p]){//依据根节点的数组下标和 里面的值相同来找到根节点 
		p=v[p];//若两个元素的根节点相同则属于同一颗树 
	}
} 
void Kruskal(AMGraph g){
	int v[g.vexnum];//需要用到并查集，看是否选出的边的两个顶点是否已经归并，避免形成回路
	for(int i=0;i<g.vexnum;i++) v[i]=i;//初始化并查集 
	int sum=0;
	
	for(int q=0;q<g.vexnum-1;q++){//连通一个图需要n-1条边，(n为顶点数) 
	int x,y;
	int  min=MaxInt;
	for(int i=0;i<g.vexnum;i++){	
		for(int j=0;j<g.vexnum;j++){ 	
			if(g.arcs[i][j] <min&&g.arcs[i][j]>0&&GetRoot(v,i)!=GetRoot(v,j)){//选出的边不能形成回路 
				min=g.arcs[i][j];
				x=i;
				y=j;
 
			}
		} 
	}
	printf("[%d %d]\n",x,y); 
	sum+=min;
	g.arcs[x][y]=0;//将这条边置零，以便选出次小边 
	g.arcs[y][x]=0;//无向图 
	v[y]=x;//将两个结点挂在一棵树上
	}
	printf("\n最短路径长度为：%d\n",sum);
} 
int main(){
	AMGraph g;
	createGraph(g);
	Prim(g,0);
	Kruskal(g);
	return 0;
}

/*
测试用例一： 
6
9
0 1 9
0 2 2 
0 3 3
1 2 7
2 3 6
1 4 8
2 4 4
3 5 5
4 5 9
测试用例
5
9
0 1 4
1 2 2
2 3 1
3 4 4
4 0 3
0 2 5
0 3 2
1 4 6
1 3 3 
*/

测试用例

• 测试用例一

• 测试用例二
  
  
  
  

• 测试用例三