Prime算法

掌握思想最重要，代码只是练习


MST_Prim(Graph G){
	int min_weight[G.vexnum];
	int adjvex[G.vexnum];
	
	for(int i=0;i<G.vexnum;i++){
		min_weight[i]=G.Edge[0][i];
		adjvex[i]=0;
	}
	
	int min_arc;  //最小权重的边 
	int min_vex;   //最小权重边的另一端节点的数组下标 
	
	for(int i=1;i<G.vexnum;i++){
		min_arc=MAX;
		for(int j=1;j<G.vexnum;j++){  //找出最小权值的边  
			if(min_weight[j]!=0 && min_weight[j]<min_arc){
				min_arc=min_weight[j];   
				min_vex=j;
			}
			min_weight[min_vex]=0;  //表示将另一个点已经添加进来了 
			for(int j=0;j<G.vexnum;j++){   //修改2个数组的值 
				if(min_weight[j]!=0 && G.Edge[min_vex][j]<min_weight[j]){
					min_weight[j]=G.Edge[min_vex][j];
					adjvex[j]=min_vex;
				}
			}
		}
	}
} 

Kruskal算法

堆排序，并查集
typedef struct Edge{
	int a,b; 边的2个端点
	int weight;  边的权值
}; 

void MST_Kruskal(Graph G,Edge *edges,int *parent){
	heap_sort(edges);  //堆排序
	Initial(parent);   //并查集的初始化
	for(int i=0;i<G.arcnum;i++){
		int a_root=find(parent,edges[i].a);  //找a端点的根节点
		int b_root=find(parent,edges[i].b);   //找b端点的根节点
		if(a_root!=b_root) Unite(parent,a_root,b_root);  //如果没有在一个集合，进行合并
	}
}