minispantree.cpp

最小生成树~~~~Kruskal算法建立最小生成树

#include <stdio.h>
#include <stdlib.h>


#define MAX_ARC_NUM 100
#define MAX_VEX_NUM 20
#define OK 1
#define ERROR 0

typedef struct {	
        int tail;     //边的起始顶点
    	int head;     //边的终止顶点
    	int weight;   //边的权值
     } arctype ;      //边的类型定义
typedef struct{
     arctype arc[MAX_ARC_NUM+1];
     int arcnum;
	 int vexnum;
}Graph;   //无向网的定义
typedef struct {
	int parent;
}TNode;
typedef struct{
	TNode nodes[MAX_VEX_NUM];
	int n;
}PTNode,*PTree;  //树的双亲表示法


int creatgraph(Graph &g){
	char filename[15];
	int t,h,w;
	FILE *fp;
	printf("请输入无向网的存储文件名（不超过十五个字符）：\n");
	scanf("%s",filename);
	if((fp = fopen(filename,"r")) == NULL){
		printf("不能打开无向网的存储文件\n");
		exit(0);
	}
	fscanf(fp,"%d,%d\n",&g.vexnum,&g.arcnum);
	
	for(int i = 1; i <= g.arcnum ; i++){
		fscanf(fp,"(%d,%d):%d\n",&t,&h,&w);
		if(t < 0 ||h < 0|| w < 0){
			printf("边(%d,%d):%d有错误\n",&t,&h,&w);
			exit(0);
		}
		else{
			g.arc[i].tail = t;
			g.arc[i].head = h;
			g.arc[i].weight = w;
		}		
	}
	fclose(fp);
	return OK;
}

int init_mfset(PTree &S,int num){
	
	S->n = num;
	for(int i = 1; i <= S->n; i++ )
		S->nodes[i].parent = -1;
	return OK;
}

int find_mfset(PTree S,int i ){
	int j;
	if(i<1 || i > S->n)  return -1;
	for(j = i; S->nodes[j].parent > 0; j = S->nodes[j].parent);
	return j;
}

int mix_mfset(PTree &S, int i ,int j){
	if(i<1 || i>S->n || j<1 || j>S->n)
		return ERROR;
	if(S->nodes[i].parent > S->nodes[j].parent){
		S->nodes[j].parent += S->nodes[i].parent;
		S->nodes[i].parent  = j;
	}
	else{
		S->nodes[i].parent += S->nodes[j].parent;
		S->nodes[j].parent  = i;
	}
	return OK;
}

void HeapAdjust(Graph &G, int s, int m){
        arctype rc = G.arc[s];
		for(int j = 2*s; j<=m; j*=2){
			if(j < m && G.arc[j].weight < G.arc[j+1].weight )  ++j;
			if(rc.weight >= G.arc[j].weight) break;
			G.arc[s] = G.arc[j]; s=j;
		}
		G.arc[s] = rc;
}


void HeapSort(Graph &G){
	for(int i = G.arcnum/2; i>0; --i)
		HeapAdjust(G , i, G.arcnum);
	for( i = G.arcnum; i>1; --i){
		arctype rc = G.arc[1];
		G.arc[1] = G.arc[i];
		G.arc[i] = rc;
		HeapAdjust(G,1,i-1);
	}
}


int Print(Graph g){
	for(int i = 1; i <= g.arcnum; i++)
		printf("(%d,%d):%d\n",g.arc[i].tail,g.arc[i].head,g.arc[i].weight);
	return OK;
}

int FPrint(Graph h){
	FILE *fp;
	if((fp = fopen("minispantree.txt","w")) == NULL){
		printf("不能打开写入文件\n");
		exit(0);
	}
	printf("最小生成树如下所示：\n");
	fprintf(fp,"最小生成树如下所示：\n");
	for(int i=1; i<=h.arcnum;i++){
		printf("(%d,%d):%d\n",h.arc[i].tail,h.arc[i].head,h.arc[i].weight);
		fprintf(fp,"(%d,%d):%d\n",h.arc[i].tail,h.arc[i].head,h.arc[i].weight);
	}
	fclose(fp);
	return OK;
}

Graph minispantree(Graph g,PTree S){
	Graph H;
	HeapSort(g);
	H.arcnum = 0;
	int m,n;
	for(int i = 1 , j = 1; i < g.vexnum && j <= g.arcnum ; j++){
		m = find_mfset(S,g.arc[j].tail);
    	n = find_mfset(S,g.arc[j].head);
		if(m != -1 && n != -1 && m !=n){
			H.arc[i] = g.arc[j];
			H.arcnum++;
			mix_mfset(S,m,n);
			i++;
		}
	}
	return H;
}

void main(){
	Graph g,h;
	PTree S;
	creatgraph(g);
	printf("无向网如下所示：\n");
	Print(g);
	if(!(S = (PTNode*)malloc(sizeof(PTNode)))) exit(0);
	init_mfset(S,g.vexnum);
	h = minispantree(g,S);
	FPrint(h);
}