#define _CRT_SECURE_NO_WARNINGS
#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[xroot].rank++;
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++;
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;
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) {
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);
main 함수에서 graph의 V와 E는 잘 입력 되엇고 edge배열또한 insert_min_heap을 통해서 잘 받은것 같은데 아무것도 출력이 안됩니다.. 중간에 printf로 계속 확인해봐도 아무것도 출력되지 않네요.. 도와주시면 사례하겠습니다
댓글을 작성하려면 로그인해야 합니다.
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로 계속 확인해봐도 아무것도 출력되지 않네요.. 도와주시면 사례하겠습니다