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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 30
#define INF 100
typedef struct {
int u;
int v;
int weight;
} Edge;
typedef struct {
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];
} DisjointSet;
typedef struct {
int numVertices;
int numEdges;
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
} Graph;
void makeSet(DisjointSet* set, int vertex) {
set->parent[vertex] = vertex;
set->rank[vertex] = 0;
}
int find(DisjointSet* set, int vertex) {
if (set->parent[vertex] != vertex) {
set->parent[vertex] = find(set, set->parent[vertex]);
}
return set->parent[vertex];
}
void unionSets(DisjointSet* set, int root1, int root2) {
if (set->rank[root1] > set->rank[root2]) {
set->parent[root2] = root1;
} else if (set->rank[root1] < set->rank[root2]) {
set->parent[root1] = root2;
} else {
set->parent[root2] = root1;
set->rank[root1]++;
}
}
int compareEdges(const void* a, const void* b) {
return ((Edge*)a)->weight - ((Edge*)b)->weight;
}
void kruskalMST(Graph* graph) {
int numVertices = graph->numVertices;
Edge result[numVertices];
int numEdges = 0;
qsort(graph->edges, graph->numEdges, sizeof(Edge), compareEdges);
DisjointSet set;
for (int v = 0; v < numVertices; v++) {
makeSet(&set, v);
}
int i = 0;
while (numEdges < numVertices - 1) {
Edge nextEdge = graph->edges[i++];
int root1 = find(&set, nextEdge.u);
int root2 = find(&set, nextEdge.v);
if (root1 != root2) {
result[numEdges++] = nextEdge;
unionSets(&set, root1, root2);
}
}
printf("Kruskal's Minimum Spanning Tree:\n");
for (int i = 0; i < numEdges; i++) {
printf("%d -- %d : %d\n", result[i].u, result[i].v, result[i].weight);
}
}
void primMST(Graph* graph) {
int numVertices = graph->numVertices;
int parent[numVertices];
int key[numVertices];
int mstSet[numVertices];
for (int v = 0; v < numVertices; v++) {
key[v] = INF;
mstSet[v] = 0;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < numVertices - 1; count++) {
int minKey = INF;
int minIndex = -1;
for (int v = 0; v < numVertices; v++) {
if (mstSet[v] == 0 && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
mstSet[minIndex] = 1;
for (int v = 0; v < numVertices; v++) {
if (graph->edges[minIndex][v] != 0 && mstSet[v] == 0 && graph->edges[minIndex][v] < key[v]) {
parent[v] = minIndex;
key[v] = graph->edges[minIndex][v];
}
}
}
printf("Prim's Minimum Spanning Tree:\n");
for (int i = 1; i < numVertices; i++) {
printf("%d -- %d : %d\n", parent[i], i, graph->edges[i][parent[i]]);
}
}
int main() {
Graph graph;
graph.numVertices = 6;
graph.numEdges = 9;
graph.edges[0].u = 0;
graph.edges[0].v = 1;
graph.edges[0].weight = 4;
graph.edges[1].u = 0;
graph.edges[1].v = 2;
graph.edges[1].weight = 3;
kruskalMST(&graph);
primMST(&graph);
return 0;
}
|