몰라

#include<stdio.h>

#include<stdlib.h>

#define MAX_VERTICES 7

#define TREE_SIZE 10

typedef struct {

int from;

int to;

int weight;

}ED;

int num[MAX_VERTICES]; //각 집합의 크기

int parent[MAX_VERTICES]; //부모노드

ED E[TREE_SIZE];

void kruskal();

int cyclecheck(int *n);

void addTree(int *n);

int main(void)

{

int i;

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

{

num[i] =1;

parent[i]=-1;

}

E[1].from = 0; E[1].to = 5; E[1].weight = 10;

E[2].from = 2; E[2].to = 3; E[2].weight = 12;

E[3].from = 1; E[3].to = 6; E[3].weight = 14;

E[4].from = 1; E[4].to = 2; E[4].weight = 16;

E[5].from = 3; E[5].to = 6; E[5].weight = 18;

E[6].from = 3; E[6].to = 4; E[6].weight = 22;

E[7].from = 4; E[7].to = 6; E[7].weight = 24;

E[8].from = 5; E[8].to = 5; E[8].weight = 25;

E[9].from = 0; E[9].to = 1; E[9].weight = 28;

kruskal();

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

printf("%d ",num[i]);

printf("\n");

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

printf("%d ",parent[i]);

return 0;

}

void kruskal()

{

int i=1,Ecount=0;

while(Ecount<MAX_VERTICES-1)

{

if(cyclecheck(&i)==1)

{

addTree(&i);

Ecount++;

}

i++;

}

}

int cyclecheck(int *n)

{

int from,to;

int result;

from = E[*n].from;

to = E[*n].to;

while(parent[to]!=-1)

{

to = parent[to];

}

while(parent[from]!=-1)

{

from = parent[from];

}

if(to==from)

result = 0;

else result = 1;

return result;

}

void addTree(int *n)

{

int from,to;

from = E[*n].from;

to = E[*n].to;

while(parent[to]!=-1)

{

to = parent[to];

}

while(parent[from]!=-1)

{

from = parent[from];

}

if(from < to)

{

parent[from]=to;

}

else{

parent[to]=from;

}

}