此题为简单的最小生成树问题，我用prim，很轻松就过了，但用kruscal写的代码老是wa。希望各位不吝赐教。
我写的prim:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define D 999999
int main(){
int n,m,i,map[100][100],lowcost[100],closet[100],x,y,z,min,sum,k;
while(scanf("%d",&n)){
if(n==0) break;
memset(map,0,sizeof(map));
memset(lowcost,999999,sizeof(lowcost));
sum=0;
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(map[x][y]!=0){
if(map[x][y]>z)
{
map[x][y]=z;
map[y][x]=z;
}
}
else{
map[x][y]=z;
map[y][x]=z;
}
}
for(i=1;i<=n;i++){
if(map[1][i]!=0){
lowcost[i]=map[1][i];
closet[i]=1;
}
}
lowcost[1]=0;
for(int j=1;j<n;j++){
min=D;
for(int d=1;d<=n;d++){
if(lowcost[d]!=0&&lowcost[d]<min){
min=lowcost[d];
k=d;
}
}
/* printf("%d",min);
system("pause");*/
sum+=min;
lowcost[k]=0;
for(int d=1;d<=n;d++){
if(map[k][d]!=0&&map[k][d]<lowcost[d]){
lowcost[d]=map[k][d];
closet[d]=k;
}
}
}
printf("%d\n",sum);
}
}
下面则是我写的kruscal:
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define MAX 100000
struct Node{ int vertex1;
int vertex2;
int weight;
struct Node *next;
};
struct relation{
int pre;
}visited[MAX];
typedef struct Node * Edge;
Edge head = NULL;
int m;
Edge read(){
int v1, v2, w,num=1;
Edge newNode = NULL, pointer = NULL;
while(num<=m){
scanf("%d %d %d", &v1, &v2, &w);
num++;
if(v1 == -1 || v2 == -1 || w == -1) break;
newNode = (Edge)malloc(sizeof(struct Node));
newNode->vertex1 = v1;
newNode->vertex2 = v2;
newNode->weight = w;
newNode->next = NULL;
pointer = head;
if(pointer == NULL)
head = newNode;
else{
if(newNode->weight < pointer->weight){
newNode->next = pointer;
head = newNode;
}
else{
while(pointer != NULL && pointer->next != NULL){
if(pointer->weight < newNode->weight&& newNode->weight < pointer->next->weight){
newNode->next = pointer->next;
pointer->next = newNode;
break;
}
pointer = pointer->next;
}
pointer->next = newNode;
}
}
}
return head;
}
int find(int x){
int t=visited[x].pre;
while(x!=visited[x].pre)
x=visited[x].pre;
while(t!=x){
visited[t].pre=x;
t=visited[t].pre;
}
return x;
}
void Uinion(int x,int y){
int x1=find(x);
int y1=find(y);
visited[x1].pre=y1;
}
/*void printLink(Edge edge){
Edge pointer = edge;
printf("\n\nEdge link : \n");
while(pointer != NULL){
printf("[%d %d]", pointer->vertex1, pointer->vertex2);
printf("(%d)",pointer->weight);
if(pointer->next != NULL)
printf(" ==> ");
pointer = pointer->next;
}
printf("\n");
}*/
void kruskal(Edge edge, int vexnum){
int visitedEdgeNum = 0, weight = 0;
//printf("\nMin generate tree : \n");
while(visitedEdgeNum < vexnum-1){
if((edge->vertex1) != find(edge->vertex2)){
// printf("[%d %d]", edge->vertex1, edge->vertex2);
// printf("(%d) ",edge->weight);
weight += edge->weight;
visitedEdgeNum++;
Uinion(edge->vertex1,edge->vertex2);
}
edge = edge->next;
if(edge == NULL){
break;
}
}
printf("%d\n", weight);
}
int main(){
int vexnum, i;
/* printf("enter vexnum and edges with weight: \n");*/
while (scanf("%d", &vexnum)!=EOF){
if(vexnum==0) break;
Edge edge = NULL;
head=NULL;
scanf("%d",&m);
for(i=1;i<=vexnum;i++){
visited[i].pre=i;
}
edge = read();
//printLink(edge);
kruskal(edge, vexnum);
}
}