利用克魯斯卡爾演算法做課程設計
① 急求，數據結構課程設計用Kruskal 演算法求最小生成樹
將城市看成是點，城市之間的距離看成是點之間的權值。
下面是PRIM演算法實現的最小生成樹代碼。，利用鄰接矩陣存儲邊的信息。程序已通過編譯了，可以直接運行。
#include <stdio.h>
#include <string.h>
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3
/*頂點字元串的最大長度+1*/
#define MAX_INFO 20
/*相關信息字元串的最大長度+1*/
typedef char VertexType[MAX_NAME];
#define INFINITY 32767
/*用整型最大值代替無窮大*/
#define MAX_VERTEX_NUM 20
/*最大頂點個數*/
typedef enum GraphKind;
/**/
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef struct
{
VRType adj;
/*頂點關系類型。對無權圖，用1（是）或0(否）表示相鄰否*/
/*對帶全圖，則為權值類型*/
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;
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;
}
int CreateAN(MGraph *G)
{/*採用數組（鄰接矩陣）表示法，構造無向網G*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("please input number of acmes and arcs in G,and there is some information in arc,if yes is 1,else is 0:");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("please input the value of %d acmes(<%d character):\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("please input %d the first and the second of acr and weigh:\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s %s %d",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("please input some information about the arc(<%d character): ",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=DN;
return 1;
}
typedef struct
{/*記錄從頂點集U到V-U的代價最小的邊的輔助數組定義*/
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int mininum(minside SZ,MGraph G)
{/*求closedege,lowcost的最小正值*/
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost;
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=*/
printf(":\n");
for(i=1;i<G.vexnum;++i)
{/*選擇其餘G.vexnum-1個頂點*/
k=mininum(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;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
}
② 使用克魯斯卡爾演算法為以下無向圖構造出一棵最小生成樹，請畫出構造的每一步驟
額我就寫出來怎麼構造最小生成樹吧。。。我也不記得這個是克魯斯卡爾演算法還是普利姆內演算法了，這倆我都容搞混了...
先選點7（這是任意的），找最小邊6將1加入樹，然後由1的那條向下的4邊將6加入樹，然後用18的邊將2加入樹，然後用5的邊將3加入樹，然後用8的邊將4加入樹，最後用12的邊將5加入樹。
③ 用克魯斯卡爾演算法求下圖的最小生成樹,要求給出求解過程.
依次找權值最小的邊相連，只要不形成環路，就一直兩兩連接下去，直到形成最小生成樹
④ C語言 課程設計 最小生成樹的詳細設計，還有能讓人理解的話解釋一下這個編程到底在做什麼事情
我已經發到你的郵箱
⑤ 克魯斯卡爾演算法
你確定要用鄰接表嗎？因為在克魯斯卡爾演算法里只需要存儲邊及費用，用鄰接表意義不大，還不好排序。
以下給出並查集實現的克魯斯卡爾演算法，求解生成網路的最小費用，並輸出生成網路里的路徑。
#include<iostream>
#include<algorithm>
using namespace std;
int p[1001],rank[1001];
int cho[1001];
struct edge
{
int u,v,w;//u表示起始點編號，v表示終點編號，w表示該路徑費用
}e[15001];
int n,m;//n表示點的個數，m表示路徑數
void Init()
{
int i;
for(i=1;i<=n;i++)
{
p[i]=i;
rank[i]=0;
}
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int Find(int t)
{
if(p[t]!=t)
{
p[t]=Find(p[t]);
}
return p[t];
}
int Union(int a,int b)
{
int x,y;
x=Find(a);
y=Find(b);
if(rank[x]>rank[y])
{
p[y]=x;
}
else
{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
Init();
sort(e,e+m,cmp);
int cnt=0,ans=0;
for(i=0;i<m;i++)
{
if(Find(e[i].u)!=Find(e[i].v))
{
cnt++;
ans+=e[i].w;
Union(e[i].u,e[i].v);
cho[++cho[0]]=i;
if(cnt==n-1)
break;
}
}
printf("%d\n",ans);
for(j=1;j<=cho[0];j++)
{
printf("%d %d\n",e[cho[j]].u,e[cho[j]].v);
}
return 0;
}
⑥ 數據結構 採用克魯斯卡爾演算法構造生成小樹，寫出過程
需要，你的結果是2棵樹（森林），結果要的是一棵樹，當然要連起來
⑦ 採用克魯斯卡爾演算法構造生成小樹，寫出過程
普利姆演算法我忘了，克魯斯卡爾演算法簡單。你就畫三張圖，每一張圖都把所有點畫出來先；第一張圖連接BD；第二張圖連接BD,BA；第三張圖連接BD，BA，AC；