Kruskal算法构造的最小生成树！！高手莫笑！！ - 数据结构与算法

楼主

问题点数：0 回复次数：3

Kruskal算法构造的最小生成树！！高手莫笑！！

这是小弟忙了好几天做出来的！！
Kruskal算法构造的最小生成树！！

由于是刚学数据结构，程序很不完善，算法很简单，望各位多多指教！

高手莫笑！！

源程序如下（最小生成树）：

#include <stdio.h>

#include <limits.h>

#define INFINITY 0

#define MaxEdge 50

#define MAX_VERTEX_NUM 10

typedef struct { /* 图的定义*/

int vexs[MAX_VERTEX_NUM]; /* 顶点信息*/

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*以矩阵存储边的信息*/

int vexnum, e; /* 顶点数，弧数 */

}Graph;

typedef struct ENode{ /*以数组存储边的信息*/

int vex1,vex2;

int weight;

}ENode;

Graph G;

ENode edgelist[MaxEdge],temp;

void CreateGraph(Graph G,int a,int b){

int i,j,k;
int start,end,weight;

k=0;
G.vexnum=a; G.e=b;

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

for(j=0;j<b;j++)

G.arcs[i][j]=INFINITY;

for(i=0;i<b;i++){

printf("Intput the arcs and its weight(format:1,3,2):\n");

scanf("%d,%d,%d",&start,&end,&weight);

getchar();

G.arcs[start-1][end-1]=weight;
G.arcs[end-1][start-1]=weight;

}

for(i=0;i<b;i++) /*将矩阵中边的信息复制到edgelist 中*/

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

if(G.arcs[i][j]){

edgelist[k].weight=G.arcs[i][j];

edgelist[k].vex1=j+1;
edgelist[k].vex2=i+1;
k++;

}

for(i=0;i<b;i++) /*按边的权重非递减将边排序*/

for(j=i+1;j<b;j++)

if(edgelist[i].weight>edgelist[j].weight){

temp=edgelist[i];
edgelist[i]=edgelist[j];
edgelist[j]=temp；
}

}

void Kruskal_MST(ENode edgelist[],int n,int e)

{/*用Kruskal算法构造最小生成树*/

int i,j,k,v1,v2,*Vset;

Vset=(int *)malloc(a*sizeof(int));

for(i=0;i<G.vexnum;i++)

Vset[i]=i;

j=0;k=0;

printf("\nThe min tree:");

while(k<a-1&&j<b-1){

v1=edgelist[j].vex1; v2=edgelist[j].vex2;

if( Vset[v1]!=Vset[v2]){

printf("\n(%d,%d),%d",v1,v2,edgelist[j].weight);

k++;

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

if(Vset[i]==Vset[v2]) Vset[i]=Vset[v1];

}

j++;

}

if(k<a-1)

printf("\nError! Can not creat the min tree!");

free(Vset);

return;

}

void main(){

char j='y';
int a,b;

clrscr(); /*清屏*/

while(j!='N'&&j!='n'){

printf("\nPlease input the numbers of vex and edge(format:3,3):\n");

scanf("%d,%d",&a,&b);

CreateGraph(G,a,b);

Kruskal_MST(edgelist,a,b);

getchar();

printf("\ncontinue(Y/N)?");

scanf("%c",&j);

}

搜索更多相关主题的帖子: 成树　 Kruskal　算法　构造　小生　

第 2 楼

得分:0

楼主。你那边的我就删了。谢谢你发出代码

生是编程人！！！！死是编程鬼！！！！颠峰人生！！！焚尽编程！！！爱已严重死机！情必须重新启动！情人已和服务器断开连接！网恋也需要重新拨号！-----激情依旧

第 3 楼

得分:0

有没有最小生成树的prims算法????????

第 4 楼

得分:0

哪位高手能帮我给下面的程序添加一个图的输入函数,周五交课程设计,急啊!!!

#include <stdio.h>
#include<stdlib.h>
#include <string.h>
#include <conio.h>
#define max_size 100
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef struct krus {
int node1;
int node2;
int vex;
}krus;

typedef struct PTNode {//树的结点结构
int data;
int parent;//双亲位置
}PTNode;

typedef struct PTree {//树的结构
PTNode nodes[max_size];
int n; //结点数
}PTree;

typedef PTree MFSet;

int initptree(MFSet* p) {
int i;
(*p).n=6;
for(i=0;i<6;++i) {
(*p).nodes[i].data=i;
(*p).nodes[i].parent=-1;
}return 0;
}

int find_mfset(MFSet S,int i) {
int j;
if(i<1||i>S.n||j>S.n) return -1;
for(j=i;S.nodes[j].parent>0;j=S.nodes[j].parent);
return j;
}

int merge_mfset(MFSet &S,int i,int j)
{
if(i<1||i>S.n||j>S.n) return -1;
else S.nodes[i].parent=j;
return 1;
}

int mix_mfset(MFSet *S,int i,int j) {

if(i<1||i>(*S).n||j>(*S).n)
return -1;
if((*S).nodes[i].parent>(*S).nodes[j].parent)
{
(*S).nodes[j].parent+=(*S).nodes[i].parent;
(*S).nodes[i].parent=j;
}
else
{
(*S).nodes[i].parent+=(*S).nodes[j].parent;
(*S).nodes[j].parent=i;
}
return 1;
}

int fix_mfset(MFSet* s,int i) {
int j,k,t;
if(i<1||i>(*s).n) return -1;
for(j=i;(*s).nodes[j].parent>0;j=(*s).nodes[j].parent);
for(k=i;k!=j;k=t) {
t=(*s).nodes[k].parent; (*s).nodes[k].parent=j;
}
return j;
}

int kruskal(void) {int n;
int grah[6][6]={{-1, 6, 1, 5,-1,-1},
{ 6,-1, 5,-1, 3,-1},
{ 1, 5,-1, 5, 6, 4},
{ 5,-1, 5,-1,-1, 2},
{-1, 3, 6,-1,-1, 6},
{-1,-1, 4, 2, 6,-1}};

krus ve[10],vetemp; MFSet tree;
int i,j,k=0,temp=1,nodex,nodey,nodevex,gen1,gen2,js=0;

for(i=0;i<6;++i) {
for(j=temp;j<6;++j) {
if(grah[i][j]!=-1) {
ve[k].node1=i; ve[k].node2=j;
ve[k].vex=grah[i][j]; ++k;
}
}
++temp;
}

initptree(&tree);

for(i=9;i>0;--i) {
for(j=0;j<i;j++) {
if(ve[j].vex>ve[j+1].vex) {
vetemp=ve[j]; ve[j]=ve[j+1]; ve[j+1]=vetemp;
}
}
}

for(i=0;i<10&&js<5;++i) {
nodex=ve[i].node1; nodey=ve[i].node2; nodevex=ve[i].vex;
gen1=find_mfset(tree,nodex); gen2=find_mfset(tree,nodey);
if(gen1!=gen2) {
++js;
mix_mfset(&tree,gen1,gen2);
printf("%d gen:%d, %d gen:%d\n",nodex,gen1,nodey,gen2);
printf("the %d:%d->%d is %d\n",i,nodex,nodey,nodevex);
}
}

return 0;

}
int main(void) {

kruskal();
return 0;
}