Kruskal C语言实现

/************************ Kruskal************************************ ************************explanation in english********************** *******************Create by Huiyue2012**************************/

#include
#include

int n;
int m;
int cm[1000];
int all=0;

typedef struct InputData{
	int F[100000];
	int T[100000];
	int M[100000];
	int state[100000];
}ID;

int CheckDataReadState（int *stateint Number）{
// 0->read;  1->no read; 
	int i;
	for（i=0;i		if（*（state+i））
			return 1;
	}
	return 0;
// return 0 read all data; 1 sill exist data no read;
}

int CertaintySetCheck（int *certainty_setint Number）{
	
	int i;
	for（i=0;i		if（*（certainty_set+i）==（Number+1））
			return 1;
	}
	return 0;
// return 0 all ID exist; 1 the set sill not full;
}

int PointWetherIn（int *CheckSetint pointint Number）{
	
	int i;
	for（i=0;i		if（*（CheckSet+i）==point）
			return 1;
	}
	return 0;
// 1 exist;0 not include; 
}


int Kruskal（ID* id）{

	int jkpmin=n+1;

	for（k=0;k		if（cm[k]			//find number in the union?
			for（p=0;p			{
				if（（cm[k]==id->F[p]）||（cm[k]==id->T[p]））{

						for（j=0;j				
							//check state is allow?
							if（id->state[j]）{
								if（min>id->M[j]）
									min=id->M[j];
							}

						}
				
				}
			}
			

		}
	}

	//update state
	for（j=0;j		if（min==id->M[j]）{
			id->state[j]=0;
			// update union
			if（cm[id->F[j]-1]==（n+1））
				cm[id->F[j]-1]=id->F[j];
			else if（cm[id->T[j]-1]==（n+1））
				cm[id->T[j]-1]=id->T[j];
		}
	}
	
	all+=min;

	//check all number over ?
	for（j=0;j		if（cm[j]==（n+1））
			return Kruskal（id）;
	}

	return all;

}

int main（）{

	int i;
	ID id;
	scanf（“%d %d“&n&m）;

	for（i=0;i		scanf（“%d %d %d“id.F+iid.T+iid.M+i）;
		id.state[i]=1;
		cm[i]=n+1;
	}
	cm[0]=1;
	printf（“%d\n“Kruskal（&id））;

	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-05-08 11:03  Kruskal\
     目录           0  2018-04-26 08:36  Kruskal\Debug\
     文件      184403  2018-03-16 16:50  Kruskal\Debug\Kruskal.exe
     文件      185708  2018-03-16 16:50  Kruskal\Debug\Kruskal.ilk
     文件      184792  2018-03-16 16:47  Kruskal\Debug\Kruskal.pch
     文件      451584  2018-03-16 16:50  Kruskal\Debug\Kruskal.pdb
     文件        6585  2018-03-16 16:50  Kruskal\Debug\main.obj
     文件       33792  2018-03-16 16:50  Kruskal\Debug\vc60.idb
     文件       53248  2018-03-16 16:50  Kruskal\Debug\vc60.pdb
     文件        4291  2018-03-15 22:28  Kruskal\Kruskal.dsp
     文件         520  2018-03-15 21:04  Kruskal\Kruskal.dsw
     文件       41984  2018-05-08 11:03  Kruskal\Kruskal.ncb
     文件       48640  2018-05-08 11:03  Kruskal\Kruskal.opt
     文件        1300  2018-03-16 16:50  Kruskal\Kruskal.plg
     文件        1787  2018-03-16 16:50  Kruskal\main.c