生成樹演算法代碼

㈠ 最小生成樹演算法，急！

已編譯確認，編譯環境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);}