cnim413   3년 전

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

#include

#define HEAP_EMPTY(n) (!n)

struct Edge

{

int src, dest, weight;

};

struct Graph

{

int V, E;

struct Edge* edge;

};

struct Graph* createGraph(int V, int E)

{

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->V = V;

graph->E = E;

graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));

return graph;

}

struct subset

{

int parent;

int rank;

int num;

int64_t totalweight;

};

int find(struct subset subsets[], int i)

{

if (subsets[i].parent != i)

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;

}

void Union(struct subset subsets[], int x, int y, int weight)

{

int xroot = find(subsets, x);

int yroot = find(subsets, y);

if (subsets[xroot].rank > subsets[yroot].rank)

{

subsets[yroot].parent = xroot;

subsets[xroot].num += subsets[yroot].num;

subsets[xroot].totalweight += weight;

}

else if (subsets[xroot].rank < subsets[yroot].rank)

{

subsets[xroot].parent = yroot;

subsets[yroot].num += subsets[xroot].num;

subsets[yroot].totalweight += weight;

}

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

subsets[xroot].num += subsets[yroot].num;

subsets[xroot].totalweight += weight;

}

}

void insert_min_heap(struct Edge* heap, struct Edge a, int* n)

{

int i;

i = ++(*n);

while ((i != 1) && (heap[i / 2].weight > a.weight))

{

heap[i] = heap[i / 2];

i = i / 2;

}

heap[i] = a;

}

struct Edge delete_min_heap(struct Edge* heap, int* n)

{

int parent, child;

struct Edge item, temp;

if (HEAP_EMPTY(*n))

{

fprintf(stderr, "The heap is empty\n");

exit(1);

}

item = heap[1];

temp = heap[(*n)--];

parent = 1; child = 2;

while (child <= *n)

{

if ((child < *n) && (heap[child].weight > heap[child + 1].weight))

child++;

if (temp.weight <= heap[child].weight) break;

heap[parent] = heap[child];

parent = child;

child *= 2;

}

heap[parent] = temp;

return item;

}

void Kruskal(struct Graph* graph, int n)

{

int V = graph->V;

int i, e = 0;

struct Edge edge;

struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));

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

{

subsets[i].parent = i;

subsets[i].rank = 0;

subsets[i].num = 1;

subsets[i].totalweight = 0;

}

printf("%d\n", V);

while (e < V - 1)

{

edge = delete_min_heap(graph->edge, &n);

int x = find(subsets, edge.src);

int y = find(subsets, edge.dest);

if (x != y)

{

Union(subsets, x, y, edge.weight);

e++;

}

}

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

{

if (subsets[i].parent == i)

{

printf("%d %lld\n", subsets[i].num, subsets[i].totalweight);

}

}

free(subsets);

}

int main(void)

{

char jooso[100], inputName[100], outputName[100], filePath[100];

int V, E, MAX_WEIGHT, i, n = 0, src, dest, weight;

struct Graph* graph;

struct Edge edge;

FILE* fp1, * fp2;

if ((fp1 = fopen("commands.txt", "r")) == NULL) {

fprintf(stderr, "Error: can not open the test file ...\n");

return 0;

}

fscanf(fp1, "%s", jooso);

fscanf(fp1, "%s", inputName);

fscanf(fp1, "%s", outputName);

strcpy(filePath, jooso);

strcat(filePath, "\\");

strcat(filePath, inputName);

if ((fp2 = fopen(filePath, "r")) == NULL) {

fprintf(stderr, "Error: can not open the test file ...\n");

return 0;

}

fscanf(fp2, "%d %d %d", &V, &E, &MAX_WEIGHT);

graph = createGraph(V, E);

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

{

fscanf(fp2, "%d %d %d", &src, &dest, &weight);

edge.src = src; edge.dest = dest; edge.weight = weight;

insert_min_heap(graph->edge, edge, &n);

}

Kruskal(graph, n);

free(graph); fclose(fp1); fclose(fp2);

return 0;

}

main 함수에서 graph의 V와 E는 잘 입력 되엇고 edge배열또한 insert_min_heap을 통해서 잘 받은것 같은데 아무것도 출력이 안됩니다.. 중간에 printf로 계속 확인해봐도 아무것도 출력되지 않네요.. 도와주시면 사례하겠습니다

댓글을 작성하려면 로그인해야 합니다.