prim和kruskal算法求最小生成树262629

prim和kruskal算法求最小生成树

#include
#include
#include
#include
#define INF  10000
typedef struct
{
	int Adj;//权值
}AdjMatrix[100][100];//邻接矩阵
typedef struct
{
	int		  Vexts[100];//顶点向量
	AdjMatrix Arcs;//临街矩阵
	int       Vexnum;//图的当前顶点数
}MGraph;
typedef struct
{
	int Vext;//顶点
	int Lowcost;//权值
}CLOSEDGE;
CLOSEDGE  closedge[100];//辅助数组
///克鲁斯卡尔
typedef struct
{
	int Vext[2];//边的两个定点
	int Adj;	//权值
}EDGE;//一条边
EDGE edge[100];//设置一百条边
int  EdgeLength=0;
void MiniSpanTree_Prim（MGraph Gint u）;
//用普利姆算法从第u个顶点除法构造网G的最小生成树T
//记录从顶点集u到v-u的代价最小边的辅助数组定义
int LocateVex（MGraph Gint u）;
//找到顶点u的位置
int Mininum（CLOSEDGE closedge[]int num）;
//找出下一个节点第k顶点
void FileRead（MGraph &G）;
void MiniSpanTree_Kruakal（MGraph G）;
//克鲁斯卡尔构造最小生成树
void RandProduction（MGraph &G）;
//随机产生图
void Print（MGraph G）;
void main（）
{
	MGraph G;
	srand（（long）time（NULL））; 
	do
	{
	//	FileRead（G）;
		RandProduction（G）;
		Print（G）;
		int choice=0;
		printf（“请输入从第几个点开始构造:\n“）;
		scanf（“%d“&choice）;
		printf（“普利姆算法:\n“）;
		MiniSpanTree_Prim（Gchoice）;
		printf（“克鲁斯科尔算法:\n“）;
		MiniSpanTree_Kruakal（G）;
		printf（“\t\t\t....按任意键继续:\n“）;
		getch（）;
		system（“cls“）;
	}while（1）;
}
void MiniSpanTree_Prim（MGraph Gint u）
{
	int k=0;
	k=LocateVex（Gu）;
	for（int j=0;j	{
		if（j!=k）
		{
			closedge[j].Vext=u;						//赋值
			closedge[j].Lowcost=G.Arcs[k][j].Adj;	//赋值
		}
	}
	closedge[k].Lowcost=0;//初始U={u};
	for（int i=1;i	{
		k=Mininum（closedgeG.Vexnum）;//找到下一个节点权值是最小的要并入U集合中
		printf（“边:%d->%d 权值:%d\n“closedge[k].VextG.Vexts[k]
			G.Arcs[closedge[k].Vext-1][G.Vexts[k]-1]）;
		closedge[k].Lowcost=0;//把第k个顶点并入U集
		for（j=0;j		{
			if（G.Arcs[k][j].Adj				&&（G.Arcs[k][j].Adj>0））//新加的点和原来已有的点的距离比较是不是较小
			{
			//	closedge[j]
				closedge[j].Vext=G.Vexts[k];
				closedge[j].Lowcost=G.Arcs[k][j].Adj;
			}
		}
	}
}
int LocateVex（MGraph Gint u）
{
	for（int i=0;i	{
		if（u==G.Vexts[i]）
		{
			return i;//返回位置
		}
	}
	return -1;
}
int Mininum（CLOSEDGE closedge[]int num）
{
	int min=0;
	bool first=true;		//寻找第一个非零点
	for（int i=0;i	{
		if（closedge[i].Lowcost>0）//在v-u点中找
		{
			if（first）
			{
				min=closedge[i].Lowcost;//这个元素为最小的
				first=false;
			}
			if（closedge[i].Lowcost			{
				min=closedge[i].Lowcost;		//将这个元素标称最小的
			}
		}
	}
	//已经找到了最小的元素了找到他的位置
	for（int j=0;j	{
		if（closedge[j].Lowcost==min）
		{
			return j;
		}
	}
	return -1;
}
void FileRead（MGraph &G）
{
	int temp=0;
	int length=0;
	int i=0;
	int j=0;
	printf（“请输入文件名:\n从（1到10）.txt中输入一个\n“）;
	char filename[20];
	fflush（stdin）;
	gets（filename）;
	FILE *in;
	in=fopen（filename“r“）;
	if（!in）
	{
		printf（“文件打开失败!\n“）;
		exit（0）;
	}
	while（!feof（in））
	{
		fscanf（in“%d“&temp）;
		if（temp==0）
		{
			temp=INF;
		}
		char ch;
		ch=fgetc（in）;
		G.Arcs[i][j].Adj=temp;
		j++;
		if（ch==‘\n

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         76  2008-11-15 14:39  最小生成树\1.txt

     文件          0  2008-11-15 20:14  最小生成树\2.txt

     文件      41984  2008-11-15 14:09  最小生成树\Debug\Prim_And_Kruskal.bsc

     文件     209002  2008-11-15 20:33  最小生成树\Debug\Prim_And_Kruskal.exe

     文件     446756  2008-11-15 20:33  最小生成树\Debug\Prim_And_Kruskal.ilk

     文件      14069  2008-11-15 20:33  最小生成树\Debug\Prim_And_Kruskal.obj

     文件      43520  2008-11-15 14:53  最小生成树\Debug\Prim_And_Kruskal.opt

     文件     222120  2008-11-15 20:20  最小生成树\Debug\Prim_And_Kruskal.pch

     文件     582656  2008-11-15 20:33  最小生成树\Debug\Prim_And_Kruskal.pdb

     文件      11503  2008-11-15 20:33  最小生成树\Debug\Prim_And_Kruskal.sbr

     文件      41984  2008-11-15 20:33  最小生成树\Debug\vc60.idb

     文件      53248  2008-11-15 20:33  最小生成树\Debug\vc60.pdb

     文件       5213  2008-11-15 20:33  最小生成树\Prim_And_Kruskal.cpp

     文件       3525  2008-11-15 14:03  最小生成树\Prim_And_Kruskal.dsp

     文件        540  2008-11-15 11:58  最小生成树\Prim_And_Kruskal.dsw

     文件      50176  2008-11-15 20:33  最小生成树\Prim_And_Kruskal.ncb

     文件      48640  2008-11-15 20:33  最小生成树\Prim_And_Kruskal.opt

     文件       1252  2008-11-15 20:33  最小生成树\Prim_And_Kruskal.plg

     目录          0  2008-11-15 20:33  最小生成树\Debug

     目录          0  2008-11-15 20:33  最小生成树

----------- ---------  ---------- -----  ----

              1776264                    20