鱼C论坛

 找回密码
 立即注册
查看: 1401|回复: 0

编写的一个Kruskal算法求最小生成树,怎么不能正确执行

[复制链接]
发表于 2015-4-28 08:58:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
//Kruskal算法
#include<stdio.h>
#include<stdlib.h>
#define v_number 5
#define Max 10

struct List{
        int v1;
        int v2;
        int weight;
        struct List *next;
};
typedef struct List Node;
typedef Node *Link;

int visited[v_number];

int Edge[10][3]={
        {1,2,7},{1,3,6},{1,4,5},{1,5,12},{2,3,14},
        {2,4,8},{2,5,8},{3,4,3},{3,5,9},{4,5,2}
};

//边权值从小到大插入
Link Insert_Edge(Link Head,Link pnew){
        Link p=Head;
        while(1){
                if(pnew->weight < Head->weight){
                        pnew->next=Head;
                        Head=pnew;
                        break;
                }
                if((pnew->weight >= p->weight)&&(pnew->weight < p->next->weight)){
                        pnew->next=p->next;
                        p->next=pnew;
                        break;
                }
                p=p->next;
        }
        return Head;
}

//建立链表
Link Create_Graph(Link Head){
        int i;
        Link pnew;
        Head=(Link)malloc(sizeof(Node));
        if(Head == NULL){
                printf("Fail\n");
                return NULL;
        }
        else{
                Head->v1=Edge[0][0];
                Head->v2=Edge[0][1];
                Head->weight=Edge[0][2];
                Head->next=NULL;
                for(i=0;i<Max;i++){
                        pnew=(Link)malloc(sizeof(Node));
                        if(pnew != NULL){
                                pnew->v1=Edge[i][0];
                                pnew->v2=Edge[i][1];
                                pnew->weight=Edge[i][2];
                                pnew->next=NULL;
                                Head=Insert_Edge(Head,pnew);
                        }
                }
                return Head;
        }
}

//打印链表
void Print_Graph(Link Head){
        Link p=Head;
        while(p != NULL){
                printf("[%d,%d]",p->v1,p->v2);
                printf("(%d)",p->weight);
                p=p->next;
        }
        printf("\n");
}

//Kruskal算法
void Kruskal(Link Head){
        Link p=Head;
        int Edge_number=0;
        int Total_Weight=0;
       
        while(Edge_number != (v_number-1)){
                if(visited[p->v1]==0 || visited[p->v2]==0){
                        printf("==>[%d,%d]",p->v1,p->v2);
                        printf("(%d)",p->weight);
                        Edge_number++;
                        Total_Weight+=p->weight;
                        visited[p->v1]=1;
                        visited[p->v2]=1;
                }
                p=p->next;
                if(p == NULL){
                        break;
                }
        }
        printf("Tatal Weight = %d",Total_Weight);
}
int main(){
        Link Head;
        int i;
        for(i=0;i<v_number;i++){
                visited[i]=0;
        }
        Head=Create_Graph(Head);
        Print_Graph(Head);
        return 0;
}

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-25 21:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表