-
Notifications
You must be signed in to change notification settings - Fork 0
/
Mst.java
79 lines (51 loc) · 1.15 KB
/
Mst.java
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
package algoAssignments;
import java.util.Scanner;
import java.util.Scanner;
public class Mst{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int[][] matrix = new int[5][5];
int[] parent = new int[5];
int min;
int u = 0;
int v = 0;
int noOfEdges = 1;
int total = 0;
for(int i = 0; i < 5; i++){
parent[i] = 0;
for(int j = 0; j < 5; j++){
matrix[i][j] = scan.nextInt();
if(matrix[i][j]==0){
matrix[i][j] = 999;
}
}
}
while(noOfEdges < 5){
min = 999;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
if(matrix[i][j] < min){
min = matrix[i][j];
u = i;
v = j;
}
}
}
while(parent[u]!=0){
u = parent[u];
}
while(parent[v]!=0){
v = parent[v];
}
if(v!=u){
noOfEdges++;
System.out.println("Edge Found: " + u + "->" + v+" Min : " + min);
total+=min;
parent[v] = u;
}
matrix[u][v] = 999;
matrix[v][u] = 999;
}
System.out.println("The weight of the minimum spanning tree is "+total);
}
}