生成树算法代码

㈠ 最小生成树算法，急！

已编译确认，编译环境vs2005/dev-cpp
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<conio.h>
#include<math.h> /* floor(),ceil(),abs() */

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/*图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作*/
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
typedef struct
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ /* 求closedge.lowcost的最小正值 */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 第一个不为0的值 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) /* 辅助数组初始化 */
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; /* 初始,U={u} */
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{ /* 选择其余G.vexnum-1个顶点 */
k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边 */
closedge[k].lowcost=0; /* 第K顶点并入U集 */
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ /* 新顶点并入U集后重新选择最小边 */
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}

int main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
return 0;
}

㈡ 最小生成树算法源程序

#include <stdio.h>
#include <stdlib.h>typedef struct{
int vexnum;//点数量
int arcnum;//边数量
int **arcs;//边指针
char *vexs;//点名称
}iGraph;
typedef struct close{
int adjvex;//
int endvex;//
int lowcost;//最小权值
}*closedge,closedges;void CreateUDN(iGraph &G);//创建无向图
int LocateVex(iGraph G,char v);//节点的顶点向量中的下标
void PrintUDN(iGraph G);//输出存储结构示意图
void MiniSpanTree_PRIM(iGraph G,closedge &minedge);//求最小生成树的算法
void PrintMinEdge(iGraph G,closedge minedge);//输出最小生成树的边
int main()
{iGraph G;<br>closedge minedge;</p><p> CreateUDN(G);<br> printf("\n");<br> MiniSpanTree_PRIM(G,minedge);<br> PrintMinEdge(G,minedge);<br> printf("\n");<br> return 0;<br>}void CreateUDN(iGraph &G)
{int i,j,k,l,cost;<br> char name1,name2;</p><p> printf("请输入顶点数和边数，且边数大于或等于顶点数，用空格符隔开：\n");<br> scanf("%d %d",&G.vexnum,&G.arcnum);<br> getchar();<br> G.vexs=(char *)malloc(G.vexnum*sizeof(char));//开辟空间<br> for(i=0;i<G.arcnum;i++)<br> G.arcs=(int **)malloc(G.arcnum*sizeof(int *));<br> for(i=0;i<G.arcnum;i++)<br> G.arcs[i]=(int *)malloc(G.arcnum*sizeof(int));<br> printf("请输入各顶点名字，回车确认：\n");<br> for(i=0;i<G.vexnum;i++)<br> {scanf("%c",&G.vexs[i]);<br> getchar();}
printf("请输入图中各边。按回车结束一条边的输入，输入结束后按回车执行，输入格式为：“端点1-端点2-权值”：\n"); for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=100000; //使边的权值初始化为最大

for(i=0;i<G.arcnum;i++)
{
scanf("%c-%c-%d",&name1,&name2,&cost);
getchar();
for(j=0;j<G.vexnum;j++)//在表中查找点
{ if(name1==G.vexs[j])
k=j;
if(name2==G.vexs[j])
l=j;
}
if(k==l)//两个点如果相同，报错
{i--;<br> printf("输入错误的数据,请重新输入\n");<br> continue;<br> } G.arcs[k][l]=cost;//无向边赋权值
G.arcs[l][k]=cost;
}//使输入的边赋值 for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(i==j)
G.arcs[i][j]=0;//如果端点相同，则不存在边
}int LocateVex(iGraph G,char v)//节点的顶点向量中的下标
{int i,m;<br> for(i=0;i<G.vexnum;i++)<br> if(v==G.vexs[i])<br> m=i;<br> return m;<br>}void PrintUDN(iGraph G)//打印模块
{int i,j;<br> printf("对应的矩阵为\n");<br> printf(" ");<br> for(i=0;i<G.vexnum;i++)<br> printf("\t%c ",G.vexs[i]);<br> printf("\n");<br> for(i=0;i<G.vexnum;i++)<br> {<br> for(j=0;j<G.vexnum+1;j++)<br> { <br> if(j==0)<br> printf("%c\t",G.vexs[i]);<br> else<br> if(G.arcs[i][j-1]==100000)//如果没有被赋值，即ij两点不连通<br> printf("NO\t");<br> else<br> printf("%d\t",G.arcs[i][j-1]);<br> }
printf("\n");
}
}void MiniSpanTree_PRIM(iGraph G,closedge &minedge)//最小生成树
{ int i,j,k,z;
int temp;
int currentmin;
k=0;
minedge=(closedge)malloc((G.vexnum+1)*sizeof(closedges));
for(j=1;j<G.vexnum;j++)
{
minedge[j-1].adjvex=k;
minedge[j-1].endvex=j;
minedge[j-1].lowcost=G.arcs[k][j];
}
for(i=0;i<G.vexnum-1;i++)
{ currentmin=minedge[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum-1;j++)
{
if(minedge[j].lowcost<currentmin)
{currentmin=minedge[j].lowcost;<br> k=j;<br> }
}
//第K个元素和第I个元素交换
temp=minedge[i].adjvex;
minedge[i].adjvex=minedge[k].adjvex;
minedge[k].adjvex=temp;
temp=minedge[i].endvex;
minedge[i].endvex=minedge[k].endvex;
minedge[k].endvex=temp;
temp=minedge[i].lowcost;
minedge[i].lowcost=minedge[k].lowcost;
minedge[k].lowcost=temp; for(j=i+1;j<G.vexnum-1;j++)
{
z=minedge[i].endvex;//Z为新找到的顶点
k=minedge[j].endvex;
if(k!=z)
{
if(G.arcs[z][k]<minedge[j].lowcost)
{
minedge[j].adjvex=z;
minedge[j].lowcost=G.arcs[z][k];//和以前的节点比较，如果边的权值小，则，即选取已有的结点中权值最小的边
}
}
}
}
}
void PrintMinEdge(iGraph G,closedge minedge)
{int i,sum;<br>sum=0;<br> printf("最小生成树对应的边为\n");<br> for(i=0;i<G.vexnum-1;i++)<br> {<br> printf("%c-%c:权值为：%d\n",G.vexs[minedge[i].adjvex],G.vexs[minedge[i].endvex],minedge[i].lowcost);<br> sum=sum+minedge[i].lowcost;<br> }
printf("最小生成树的权值为：%d",sum);
}

㈢ 求最小生成树的kruska算法，效率尽量高，尽量多点注释！c++代码

/*
基本算法思想：
为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。
具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。

用并查积 和 克鲁是卡尔算法实现查找最短边
利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
*/
/*下面的代码输入n个节点，然后输入n*（n-1）/2条边及权值，输出是连通这些边的最小权值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始点
int v; //终结点
int w; //权重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //从小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父亲
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //并查集初始化，每个节点到父亲是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //点edge[i].u的父亲是x
y=find(edge[i].v); //点edge[i].v的父亲是y
if(x!=y) //判断是否会路
{
count++; //加上一条边
p[x]=y; //把x和y加入统一个集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //输入n个节点
{
int i;
for(i=0;i<n*(n-1)/2;i++) //输入 n*（n-1）/2条边
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示点edge[i].u和点edge[i].v之间的权重为 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

楼主，这可是本人一个字一个字敲出来点，要给分啊

㈣ c++求最小生成树prim算法,我捣鼓2天了,真心不会改了,求指导感激不尽啊

你的代码太乱，给你这个，添加了注释，容易看懂：

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

usingnamespacestd;

#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
	doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
	charvexs[MAX_VERTEX_NUM];//节点数组
	AdjMatrixarcs;//邻接矩阵
	intvexnum,arcnum;//图的当前节点数和弧数
}MGraph;
typedefstructPnode//用于普利姆算法
{
	charadjvex;//节点
	doublelowcost;//权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
	charch1;//节点1
	charch2;//节点2
	doublevalue;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//构造无向加权图的邻接矩阵
{
	inti,j,k;
	cout<<"请输入图中节点个数和边/弧的条数：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"请输入节点：";
	for(i=0;i<G.vexnum;++i)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;++i)//初始化数组
	{
		for(j=0;j<G.vexnum;++j)
		{
			G.arcs[i][j].adj=MAX;
		}
	}
	cout<<"请输入一条边依附的定点及边的权值："<<endl;
	for(k=0;k<G.arcnum;++k)
	{
		cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
		i=LocateVex(G,dgevalue[k].ch1);
		j=LocateVex(G,dgevalue[k].ch2);
		G.arcs[i][j].adj=dgevalue[k].value;
		G.arcs[j][i].adj=G.arcs[i][j].adj;
	}
	returnOK;
}
intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置
{
	inta;
	for(inti=0;i<G.vexnum;i++)
	{
		if(G.vexs[i]==ch)
			a=i;
	}
	returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树
{
	inti,j,k;
	Closedgeclosedge;
	k=LocateVex(G,u);
	//将该顶点到其他所有的顶点权值赋值给closedge
	for(j=0;j<G.vexnum;j++)
	{
		if(j!=k)
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	}
	closedge[k].lowcost=0;
	for(i=1;i<G.vexnum;i++)
	{
		//找到权值最小的顶点，记录到k
		k=Minimum(G,closedge);
		cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
		//清零，方便寻找下一个顶点
		closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;++j)
		{
			//依次比较上个顶点和当前顶点与剩余顶点的权值，将小的赋值给closedge
			if(G.arcs[k][j].adj<closedge[j].lowcost)
			{
				closedge[j].adjvex=G.vexs[k];
				closedge[j].lowcost=G.arcs[k][j].adj;
			}
		}
	}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
	inti,j;
	doublek=1000;
	for(i=0;i<G.vexnum;i++)
	{
		if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
		{
			k=closedge[i].lowcost;
			j=i;
		}
	}
	returnj;
}

voidmain()
{
	inti,j;
	MGraphG;
	charu;
	Dgevaluedgevalue;
	CreateUDG(G,dgevalue);
	cout<<"图的邻接矩阵为："<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			cout<<G.arcs[i][j].adj<<"";
		cout<<endl;
	}
	cout<<"=============普利姆算法===============
";
	cout<<"请输入起始点：";
	cin>>u;
	cout<<"构成最小代价生成树的边集为：
";
	MiniSpanTree_PRIM(G,u);
}

㈤ C语言算法求解：对任意给定的网络（顶点数和边数自定），设计算法生成它的最小生成树。

上一个图和代码：

图1为要创建的图，图2为对应的最小生成树

代码为：

//图论之最小生成树：prim算法实现

#include"stdio.h"

#include"malloc.h"

//声明

voidoutput(structadjacentlisthead*alh,intmapsize);

structadjacentlistson//邻接表项结构体

{

intsonelement;

intquanvalue;

structadjacentlistson*next;

};

structadjacentlisthead//邻接表头结构体

{

charflag;

intelement;

intcurqvalue;

structadjacentlisthead*previous;

structadjacentlistson*startson;

};

structadjacentlisthead*mapinitialnize(intmapsize)//初始化图函数

{

structadjacentlisthead*alh=NULL;

structadjacentlistson*newnode=NULL;

inti,x,y,z;

alh=malloc(sizeof(structadjacentlisthead)*mapsize);

if(alh==NULL)

returnNULL;

for(i=0;i<mapsize;i++)

{

alh[i].flag=0;

alh[i].element=i+1;

alh[i].curqvalue=0;

alh[i].previous=NULL;

alh[i].startson=NULL;

}

scanf("%d%d%d",&x,&y,&z);

while(x&&y)//直到输入的x,y中至少有一个0为止

{

newnode=malloc(sizeof(structadjacentlistson));

newnode->sonelement=y;

newnode->quanvalue=z;

newnode->next=alh[x-1].startson;

alh[x-1].startson=newnode;

scanf("%d%d%d",&x,&y,&z);

}

returnalh;

}

intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小权值对应的结点

{

inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;

for(i=0;i<mapsize;i++)

{

if(alh[i].flag==0&&alh[i].curqvalue!=0)

{

if(alh[i].curqvalue<minvalue)

{

minvalue=alh[i].curqvalue;

minplace=i+1;//

}

}

}

returnminplace;

}

voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成树

{

structadjacentlistson*alstmp=NULL;

intcurplace=startplace;

while(curplace)

{

alstmp=alh[curplace-1].startson;

alh[curplace-1].flag=1;//正在访问

while(alstmp)

{

if(alh[alstmp->sonelement-1].flag==0)

{

if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比较方法与有权图有一点不同

{

alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;

alh[alstmp->sonelement-1].previous=&alh[curplace-1];

}

}

alstmp=alstmp->next;

}

curplace=findminnode(alh,mapsize);//通过函数找到最小的一个结点

}

}

voidoutput(structadjacentlisthead*alh,intmapsize)

{

inti;

for(i=0;i<mapsize;i++)

{

printf("%d点的权值为：%d ",i+1,alh[i].curqvalue);

}

printf("................................................... ");

}

intmain()

{

structadjacentlisthead*alh=NULL;

intmapsize=7,startplace=1;

alh=mapinitialnize(mapsize);

findthemintree(alh,startplace,mapsize);

output(alh,mapsize);

}

输入数据对应第一图：

122

134

141

212

243

2510

314

342

365

411

423

432

457

468

474

5210

547

576

635

648

671

744

756

761

000

㈥ 用prim算法的思想，用C语言编写出最小生成树的方法的代码

PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}

㈦ C++最小生成树，求全代码

实在抱歉，昨天的代码有点小错误，做下改正：//Minim_tree.cpp#include "Minim_tree.h"
#include <iostream>
using namespace std;Edge::Edge()
{}
Minim_tree::Minim_tree()
{
this->city = 0;
this->line = 0;
this->Ed_len = 1;
this->Re_len = 1;
this->CreatEdgesetArray();
}void Minim_tree::CreatEdgesetArray() //构建无线网络
{
int cit,lin,i,j,w;
cout<<"输入城市数,网络数:"<<endl;
scanf("%d %d",&cit,&lin);
this->city = cit;
this->line = lin;
cout<<"请输入各网络边："<<endl;
for(int k=1;k<=this->line;k++)
{
fflush(stdin);
scanf("%d %d %d",&i,&j,&w);
this->EderSet[k].fromvex = i;
this->EderSet[k].endvex = j;
this->EderSet[k].weight = w;
}
this->SetOrder();
}void Minim_tree::SetOrder() //按权值升序排序
{
Edge temp;
for(int i = 1;i<=this->line-1;i++)
for(int j=i+1;j<=this->line;j++)
{
if(this->EderSet[i].weight>this->EderSet[j].weight)
{
temp = this->EderSet[i];
this->EderSet[i] = this->EderSet[j];
this->EderSet[j] = temp;
}
}
for(int i=1;i<=this->line-1;i++)
cout<<this->EderSet[i].fromvex<<","<<this->EderSet[i].endvex<<","<<this->EderSet[i].weight<<endl;
}void Minim_tree::Cruskal()
{
int matrix[E][E]; //此集合用来判断选定的边是否符合克鲁斯卡尔算法的条件
for(int i=1;i<=this->line;i++) //初始化集合，使每个懂点分属于对应的集合
for(int j=1;j<=this->line;j++)
{
if(i==j)
matrix[i][j]=1; // 每一个点和它自身都是连通的
else
matrix[i][j]=0;
}
int k=1 ,m1,m2;
while(k<this->line)
{
for(int i=1;i<=this->line;i++) //取边所在两定点集合所在的序号
{
if(matrix[i][this->EderSet[this->Ed_len].fromvex] == 1)
m1=i;
if(matrix[i][this->EderSet[this->Ed_len].endvex] == 1)
m2=i;
}
if(m1!=m2) //若不等则没有连通
{
this->Resul_Set[this->Re_len] = this->EderSet[this->Ed_len];
this->Re_len++;

for(int j=1;j<=this->line;j++)
{
matrix[m1][j] = matrix[m1][j]||matrix[m2][j]; //合并两个集合
matrix[m2][j] = 0; //置为空集
}
}
this->Ed_len++;
k++;
}
}
void Minim_tree::Print()
{
cout<<"根据Cruslkal算法得出以下结果（不唯一）:"<<endl;
for(int i=1;i<this->Re_len;i++)
{
cout<<this->Resul_Set[i].fromvex<<","<<this->Resul_Set[i].endvex<<","<<this->Resul_Set[i].weight<<endl;
}
}Minim_tree::~Minim_tree(void)
{}

㈧ 求无向连通图的生成树（用c语言设计程序）

不知道你要的是不是这个 完整实现如下： #define INFINITY 65535typedef int status;# include <stdio.h># include <stdlib.h># include <conio.h># include "string.h"# define maxlen 10typedef struct{ char vexs[maxlen][maxlen];/*顶点信息集合,我们用它来存入顶点名字*/ int vexnum,arcnum;/*顶点数和边数*/ int arcs[maxlen][maxlen];/*邻接矩阵*/}graph;//定位输入节点的名称int LocateVex(graph G,char u[maxlen]){int i;for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1;} void prim(graph &g)/*最小生成树*/{ int i,j,k,min,w,flag; int lowcost[maxlen];/*权值*/ int closet[maxlen];/*最小生成树结点*/ char va[maxlen],vb[maxlen]; //初始化邻接矩阵 //printf("请输入顶点数和边数：\n"); //scanf("%d%d",&g.vexnum,&g.arcnum); g.vexnum=6; g.arcnum=10; printf("请输入顶点信息(我们这里指名字)：\n"); for(int j=0;j<g.vexnum;j++) scanf("%s",g.vexs[j]); for(i=0;i<g.vexnum;++i) for(j=0;j<g.vexnum;++j)//初始化邻接矩阵 { g.arcs[i][j]=INFINITY; //任意两个顶点间距离为无穷大。 }//for /*printf("请输入%d条弧的弧尾 弧头 权值（以空格为间隔)\n",g.arcnum); for(k=0;k<g.arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w);//用%*c吃掉回车符 i=LocateVex(g,va); //注意，这里定义的是char va[5]，也就是说va是首地址 j=LocateVex(g,vb); g.arcs[i][j]=w; //无向网 g.arcs[j][i]=w; //无向网 }//for */ g.arcs[0][1]=6; g.arcs[1][0]=6; g.arcs[0][2]=1; g.arcs[2][0]=1; g.arcs[0][3]=5; g.arcs[3][0]=5; g.arcs[1][2]=5; g.arcs[2][1]=5; g.arcs[1][4]=3; g.arcs[4][1]=3; g.arcs[2][3]=5; g.arcs[3][2]=5; g.arcs[2][4]=6; g.arcs[4][2]=6; g.arcs[2][5]=4; g.arcs[5][2]=4; g.arcs[3][5]=2; g.arcs[5][3]=2; g.arcs[4][5]=6; g.arcs[5][4]=6; printf("最小生成树的边为:\n"); for(i=1;i<g.vexnum;i++) { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[0]=0; //初始v1是属于集合U的，即设它是最小生成树中节点的一员 j=1; //V是顶点集合 for(i=1;i<g.vexnum;i++) { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; //记录当前要加入集合U的节点号 }//if if(i==1) flag=0; else flag=closet[k]; //还没有加入集合U的节点的closet[]值是 //记录了上一次加入集合U的节点号 closet[k]=0; //将刚刚找到的点加入到集合U中 printf("(%s,%s),",g.vexs[k],g.vexs[flag]);//输出刚刚找到的最小生成树树枝 for(j=1;j<g.vexnum;j++) if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; //更新lowcost[]的值，且在还没有加入U集合的 //的closet[]中记录刚刚加入U集合的节点号以备 //下一循环中输出用 closet[j]=k; } }} int main(){graph g;prim(g);}