| 50 | |
| 51 | // Applying Krushkal Algorithm |
| 52 | void KruskalAlgo() { |
| 53 | Edge result[] = new Edge[vertices]; |
| 54 | int e = 0; |
| 55 | int i = 0; |
| 56 | for (i = 0; i < vertices; ++i) |
| 57 | result[i] = new Edge(); |
| 58 | |
| 59 | // Sorting the edges |
| 60 | Arrays.sort(edge); |
| 61 | subset subsets[] = new subset[vertices]; |
| 62 | for (i = 0; i < vertices; ++i) |
| 63 | subsets[i] = new subset(); |
| 64 | |
| 65 | for (int v = 0; v < vertices; ++v) { |
| 66 | subsets[v].parent = v; |
| 67 | subsets[v].rank = 0; |
| 68 | } |
| 69 | i = 0; |
| 70 | while (e < vertices - 1) { |
| 71 | Edge next_edge = new Edge(); |
| 72 | next_edge = edge[i++]; |
| 73 | int x = find(subsets, next_edge.src); |
| 74 | int y = find(subsets, next_edge.dest); |
| 75 | if (x != y) { |
| 76 | result[e++] = next_edge; |
| 77 | Union(subsets, x, y); |
| 78 | } |
| 79 | } |
| 80 | for (i = 0; i < e; ++i) |
| 81 | System.out.println(result[i].src + " - " + result[i].dest + ": " + result[i].weight); |
| 82 | } |
| 83 | |
| 84 | public static void main(String[] args) { |
| 85 | int vertices = 6; // Number of vertices |