-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathPrim.c
More file actions
79 lines (63 loc) · 1.55 KB
/
Prim.c
File metadata and controls
79 lines (63 loc) · 1.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define INF 1000L
typedef struct GraphType {
int n;
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
bool selected[MAX_VERTICES];
int distance[MAX_VERTICES];
int getMinVertex(int n) {
int v, i;
for (i = 0; i < n; i++) {
if (!selected[i]) {
v = i;
break;
}
}
for (i = 0; i < n; i++) {
if (!selected[i] && (distance[i] < distance[v])) {
v = i;
}
}
return v;
}
void prim(GraphType* g, int s) {
int i, u, v;
for (u = 0; u < g->n; u++) {
distance[u] = INF;
}
distance[s] = 0;
for (i = 0; i < g->n; i++) {
u = getMinVertex(g->n);
selected[u] = true;
if (distance[u] == INF) {
return;
}
printf("정점 %d 추가\n", u);
for (v = 0; v < g->n; v++) {
if (g->weight[u][v] != INF) {
if (!selected[v] && g->weight[u][v] < distance[v]) {
distance[v] = g->weight[u][v];
}
}
}
}
}
int main(void) {
GraphType g = { 7,
{
{ 0, 29, INF, INF, INF, 10, INF },
{ 29, 0, 16, INF, INF, INF, 15 },
{ INF, 16, 0, 12, INF, INF, INF },
{ INF, INF, 12, 0, 22, INF, 18 },
{ INF, INF, INF, 22, 0, 27, 25 },
{ 10, INF, INF, INF, 27, 0, INF },
{ INF, 15, INF, 18, 25, INF, 0 }
}
};
prim(&g, 0);
return 0;
}