Prim’s Algorithm is a greedy algorithm used to find the minimum spanning tree of a weighted undirected graph. It starts by selecting a random vertex from the graph and repeatedly adding the closest vertex that has not yet been added to the tree. The algorithm maintains a priority queue of edges with their weights and selects the minimum-weight edge that connects a vertex in the tree to a vertex not yet in the tree. This process is repeated until all vertices are included in the tree. Prim’s Algorithm is widely used in network design, transportation planning, and other optimization problems.
import java.util.*
class Graph(private val vertices: Int) {
private val adjacencyMatrix = Array(vertices) { IntArray(vertices) }In this code, we first define a Graph class that represents an undirected weighted graph using an adjacency matrix. The Graph class has a vertices field that stores the number of vertices in the graph, and an adjacencyMatrix field that stores the weight of the edges between each pair of vertices.
fun addEdge(u: Int, v: Int, weight: Int) {
adjacencyMatrix[u][v] = weight
adjacencyMatrix[v][u] = weight
}We then define an addEdge method that adds an edge between two vertices with a given weight to the adjacency matrix.
fun primMST() {
val key = IntArray(vertices) { Int.MAX_VALUE }
val parent = IntArray(vertices) { -1 }
val visited = BooleanArray(vertices) { false }
key[0] = 0
val pq: PriorityQueue<Node> = PriorityQueue(vertices, Node())
pq.offer(Node(0, 0))
while (!pq.isEmpty()) {
val u = pq.poll().vertex
visited[u] = true
for (v in 0 until vertices) {
if (adjacencyMatrix[u][v] != 0 && !visited[v] && adjacencyMatrix[u][v] < key[v]) {
parent[v] = u
key[v] = adjacencyMatrix[u][v]
pq.offer(Node(v, key[v]))
}
}
}
println("Edges in MST:")
for (i in 1 until vertices) {
println(parent[i].toString() + " - " + i.toString() + " (" + adjacencyMatrix[i][parent[i]].toString() + ")")
}
}
}The primMST method is the heart of the Prim’s Algorithm. It starts by initializing three arrays: key, parent, and visited. The key array keeps track of the minimum weight of the edge connecting a vertex to the MST, the parent array keeps track of the parent of each vertex in the MST, and the visited array keeps track of which vertices have already been included in the MST.
We start with the first vertex as the root of the MST, and add its neighbors to a priority queue pq based on their weight. We then repeatedly extract the vertex with the minimum weight from pq, add it to the MST, and update the key, parent, and visited arrays based on its neighbors.
import java.util.*
class Graph(private val vertices: Int) {
private val adjacencyMatrix = Array(vertices) { IntArray(vertices) }
fun addEdge(u: Int, v: Int, weight: Int) {
adjacencyMatrix[u][v] = weight
adjacencyMatrix[v][u] = weight
}
fun primMST() {
val key = IntArray(vertices) { Int.MAX_VALUE }
val parent = IntArray(vertices) { -1 }
val visited = BooleanArray(vertices) { false }
key[0] = 0
val pq: PriorityQueue<Node> = PriorityQueue(vertices, Node())
pq.offer(Node(0, 0))
while (!pq.isEmpty()) {
val u = pq.poll().vertex
visited[u] = true
for (v in 0 until vertices) {
if (adjacencyMatrix[u][v] != 0 && !visited[v] && adjacencyMatrix[u][v] < key[v]) {
parent[v] = u
key[v] = adjacencyMatrix[u][v]
pq.offer(Node(v, key[v]))
}
}
}
println("Edges in MST:")
for (i in 1 until vertices) {
println(parent[i].toString() + " - " + i.toString() + " (" + adjacencyMatrix[i][parent[i]].toString() + ")")
}
}
}
class Node(val vertex: Int = 0, val weight: Int = 0) : Comparator<Node> {
override fun compare(node1: Node, node2: Node): Int {
return node1.weight - node2.weight
}
}
fun main() {
val graph = Graph(5)
graph.addEdge(0, 1, 2)
graph.addEdge(0, 3, 6)
graph.addEdge(1, 2, 3)
graph.addEdge(1, 3, 8)
graph.addEdge(1, 4, 5)
graph.addEdge(2, 4, 7)
graph.addEdge(3, 4, 9)
graph.primMST()
}Finally, in the main function, we create a new Graph object with 5 vertices and add edges between them using the addEdge method.