| 
 | 
 
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册  
 
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; 
} 
 
 |   
 
 
 
 |