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