Kruskal’s algorithm finds a set of edges, which connected together create a tree with the minimal total weight – minimum spanning tree.
Read more on wikipedia.
Input
n m v(1) v(2) w(1,2) (m times) ... v(x) v(y) w(x,y)
n – number of vertices
m – number of edges
v(x) v(y) w(x,y) – edge between v(x) and v(y) with weight w(x,y)
Sample input
6 10 1 2 2 1 6 1 1 5 3 4 1 5 2 6 2 2 3 5 4 3 4 3 5 4 4 5 4 5 6 3
Output
The weight of a minimum spanning tree.
Complexity
First we need to sort edges in O(|E|log|E|) time, then unionSets and find operations can run in O(|V|) time in worst case, therefore whole algorithm runs in:
O(|E|log|E| + |E|·|V|) = O(|E| · (log|E| + |V|))
Source code
|
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 |
#include <stdio.h> struct Edge { int a, b; int weight; }; struct Vertex { int id; Vertex * parent; int rank; }; void sort(Edge * edges, int start, int end) { int d = edges[(start + end) / 2].weight; int i = start, j = end; Edge tmp; do { while (d > edges[i].weight) i++; while (d < edges[j].weight) j--; if (i <= j) { tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; i++; j--; } } while (i <= j); if (start < j) sort(edges, start, j); if (i < end) sort(edges, i, end); } void makeSet(Vertex * v) { v->parent = NULL; v->rank = 0; } Vertex * find(Vertex * v) { while (v->parent != NULL) v = v->parent; return v; } void unionSets(Vertex * x, Vertex * y) { Vertex * xRoot = find(x); Vertex * yRoot = find(y); if (xRoot->rank > yRoot->rank) yRoot->parent = xRoot; else if (xRoot->rank < yRoot->rank) xRoot->parent = yRoot; else if (xRoot != yRoot) { yRoot->parent = xRoot; xRoot->rank++; } } int main() { //Kruskal's Algorithm int v, e; scanf("%d %d", &v, &e); Edge * edges = new Edge[e]; for (int i = 0; i < e; i++) scanf("%d %d %d", &edges[i].a, &edges[i].b, &edges[i].weight); sort(edges, 0, e - 1); //disjoint-set Vertex * vertices = new Vertex[v + 1]; for (int i = 0; i <= v; i++) { vertices[i].id = i + 1; makeSet(&vertices[i]); } int count = 0; long sum = 0; for (int i = 0; i < e; i++) { if (find(&vertices[edges[i].a]) != find(&vertices[edges[i].b])) { unionSets(&vertices[edges[i].a], &vertices[edges[i].b]); sum += edges[i].weight; count++; } if (count == v - 1) break; } printf("%ld", sum); return 0; } |
