Skip to content

Commit 62c9309

Browse files
HardvanHardvan
authored
Enhance docs, remove main, add tests in PrimMST (TheAlgorithms#5969)
1 parent ce3dd01 commit 62c9309

File tree

3 files changed

+72
-66
lines changed

3 files changed

+72
-66
lines changed

‎DIRECTORY.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -852,6 +852,7 @@
852852
* [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
853853
* [KruskalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java)
854854
* [MatrixGraphsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/MatrixGraphsTest.java)
855+
* [PrimMSTTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/PrimMSTTest.java)
855856
* [TarjansAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithmTest.java)
856857
* [WelshPowellTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/WelshPowellTest.java)
857858
* hashmap

‎src/main/java/com/thealgorithms/datastructures/graphs/PrimMST.java

Lines changed: 17 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,17 @@
11
package com.thealgorithms.datastructures.graphs;
22

33
/**
4-
* A Java program for Prim's Minimum Spanning Tree (MST) algorithm. adjacency
5-
* matrix representation of the graph
4+
* A Java program for Prim's Minimum Spanning Tree (MST) algorithm.
5+
* Adjacency matrix representation of the graph.
66
*/
7-
class PrimMST {
7+
public class PrimMST {
88

99
// Number of vertices in the graph
10-
1110
private static final int V = 5;
1211

13-
// A utility function to find the vertex with minimum key
14-
// value, from the set of vertices not yet included in MST
12+
// A utility function to find the vertex with the minimum key
13+
// value, from the set of vertices not yet included in the MST
1514
int minKey(int[] key, Boolean[] mstSet) {
16-
// Initialize min value
1715
int min = Integer.MAX_VALUE;
1816
int minIndex = -1;
1917

@@ -27,84 +25,37 @@ int minKey(int[] key, Boolean[] mstSet) {
2725
return minIndex;
2826
}
2927

30-
// A utility function to print the constructed MST stored in
31-
// parent[]
32-
void printMST(int[] parent, int n, int[][] graph) {
33-
System.out.println("Edge Weight");
34-
for (int i = 1; i < V; i++) {
35-
System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]);
36-
}
37-
}
38-
39-
// Function to construct and print MST for a graph represented
40-
// using adjacency matrix representation
41-
void primMST(int[][] graph) {
42-
// Array to store constructed MST
43-
int[] parent = new int[V];
44-
45-
// Key values used to pick minimum weight edge in cut
46-
int[] key = new int[V];
28+
// Function to construct MST for a graph using adjacency matrix representation
29+
public int[] primMST(int[][] graph) {
30+
int[] parent = new int[V]; // Array to store constructed MST
31+
int[] key = new int[V]; // Key values to pick minimum weight edge
32+
Boolean[] mstSet = new Boolean[V]; // Vertices not yet included in MST
4733

48-
// To represent set of vertices not yet included in MST
49-
Boolean[] mstSet = new Boolean[V];
50-
51-
// Initialize all keys as INFINITE
34+
// Initialize all keys as INFINITE and mstSet[] as false
5235
for (int i = 0; i < V; i++) {
5336
key[i] = Integer.MAX_VALUE;
5437
mstSet[i] = Boolean.FALSE;
5538
}
5639

57-
// Always include first 1st vertex in MST.
58-
key[0] = 0; // Make key 0 so that this vertex is
59-
// picked as first vertex
40+
// Always include the first vertex in MST
41+
key[0] = 0; // Make key 0 to pick the first vertex
6042
parent[0] = -1; // First node is always root of MST
6143

6244
// The MST will have V vertices
6345
for (int count = 0; count < V - 1; count++) {
64-
// Pick thd minimum key vertex from the set of vertices
65-
// not yet included in MST
46+
// Pick the minimum key vertex not yet included in MST
6647
int u = minKey(key, mstSet);
67-
68-
// Add the picked vertex to the MST Set
6948
mstSet[u] = Boolean.TRUE;
7049

71-
// Update key value and parent index of the adjacent
72-
// vertices of the picked vertex. Consider only those
73-
// vertices which are not yet included in MST
74-
for (int v = 0; v < V; v++) // Update the key only if graph[u][v] is smaller than key[v] // mstSet[v] is
75-
// false for vertices not yet included in MST // graph[u][v] is non zero only
76-
// for adjacent vertices of m
77-
{
50+
// Update key value and parent index of adjacent vertices of the picked vertex
51+
for (int v = 0; v < V; v++) {
7852
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
7953
parent[v] = u;
8054
key[v] = graph[u][v];
8155
}
8256
}
8357
}
8458

85-
// print the constructed MST
86-
printMST(parent, V, graph);
87-
}
88-
89-
public static void main(String[] args) {
90-
/* Let us create the following graph
91-
2 3
92-
(0)--(1)--(2)
93-
| / \ |
94-
6| 8/ \5 |7
95-
| / \ |
96-
(3)-------(4)
97-
9 */
98-
PrimMST t = new PrimMST();
99-
int[][] graph = new int[][] {
100-
{0, 2, 0, 6, 0},
101-
{2, 0, 3, 8, 5},
102-
{0, 3, 0, 0, 7},
103-
{6, 8, 0, 0, 9},
104-
{0, 5, 7, 9, 0},
105-
};
106-
107-
// Print the solution
108-
t.primMST(graph);
59+
return parent; // Return the MST parent array
10960
}
11061
}

‎src/test/java/com/thealgorithms/datastructures/graphs/PrimMSTTest.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.thealgorithms.datastructures.graphs;
2+
3+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class PrimMSTTest {
8+
9+
private final PrimMST primMST = new PrimMST();
10+
11+
@Test
12+
public void testSimpleGraph() {
13+
// Test graph with 5 nodes and weighted edges
14+
int[][] graph = {{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0}};
15+
16+
int[] expectedParent = {-1, 0, 1, 0, 1};
17+
int[] actualParent = primMST.primMST(graph);
18+
19+
assertArrayEquals(expectedParent, actualParent);
20+
}
21+
22+
@Test
23+
public void testDisconnectedGraph() {
24+
// Test case with a disconnected graph (no valid MST)
25+
int[][] graph = {{0, 1, 0, 0, 0}, {1, 0, 2, 0, 0}, {0, 2, 0, 3, 0}, {0, 0, 3, 0, 4}, {0, 0, 0, 4, 0}};
26+
27+
int[] expectedParent = {-1, 0, 1, 2, 3}; // Expected MST parent array
28+
int[] actualParent = primMST.primMST(graph);
29+
30+
assertArrayEquals(expectedParent, actualParent);
31+
}
32+
33+
@Test
34+
public void testAllEqualWeightsGraph() {
35+
// Test case where all edges have equal weight
36+
int[][] graph = {{0, 1, 1, 1, 1}, {1, 0, 1, 1, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}};
37+
38+
int[] expectedParent = {-1, 0, 0, 0, 0}; // Expected MST parent array (any valid spanning tree)
39+
int[] actualParent = primMST.primMST(graph);
40+
41+
assertArrayEquals(expectedParent, actualParent);
42+
}
43+
44+
@Test
45+
public void testSparseGraph() {
46+
// Test case with a sparse graph (few edges)
47+
int[][] graph = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 0}};
48+
49+
int[] expectedParent = {-1, 0, 1, 2, 3}; // Expected MST parent array
50+
int[] actualParent = primMST.primMST(graph);
51+
52+
assertArrayEquals(expectedParent, actualParent);
53+
}
54+
}

0 commit comments

Comments
 (0)