Page 113 - Algorithms Notes for Professionals

Enew[] = {}
while Vnew is not equal to V
u -> a node from Vnew
v -> a node that is not in Vnew such that edge u-v has the minimum cost
// if two nodes have same weight, pick any of them
add v to Vnew
add edge (u, v) to Enew
end while
Return Vnew and Enew

Complexity:

Time complexity of the above naive approach is O(V²). It uses adjacency matrix. We can reduce the complexity
using priority queue. When we add a new node to Vnew, we can add its adjacent edges in the priority queue. Then
pop the minimum weighted edge from it. Then the complexity will be: O(ElogE), where E is the number of edges.
Again a Binary Heap can be constructed to reduce the complexity to O(ElogV).

The pseudo-code using Priority Queue is given below:

Procedure MSTPrim(Graph, source):
for each u in V
key[u] := inf
parent[u] := NULL
end for
key[source] := 0
Q = Priority_Queue()
Q = V
while Q is not empty
u -> Q.pop
for each v adjacent to i
if v belongs to Q and Edge(u,v) < key[v] // here Edge(u, v) represents
// cost of edge(u, v)
parent[v] := u
key[v] := Edge(u, v)
end if
end for
end while

Here key[] stores the minimum cost of traversing node-v. parent[] is used to store the parent node. It is useful for
traversing and printing the tree.

Below is a simple program in Java:

import java.util.*;

public class Graph
{
private static int infinite = 9999999;
int[][] LinkCost;
int NNodes;
Graph(int[][] mat)
{
int i, j;
NNodes = mat.length;
LinkCost = new int[NNodes][NNodes];
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
{

colegiohispanomexicano.net – Algorithms Notes 109