Posted on by Kalkicode
Code Graph

# Prim's algorithm using adjacency list

Prim's is an greedy algorithm, which are used to find a minimum spanning tree of a weighted undirected graph. Let us understand the used terminology of prim's algorithm.

What is graph? : A graph is a collection of nodes called vertices, and a link that connects two nodes is called an edge of the graph. For example.

The edge of graph are provide a path between two nodes. Using of edges is decided the type of graph. For example.

What is Undirected graph? : Undirected graph each link is connected to two nodes. And in this graph link are not have any direction means using of this edges are traversed in both direction.

What is Weighted of edge? : Weighted graph is assigned a number to each edge which represents distance or weight to an edge. its also known as edge-weighted graph. The weight of the edge can be positive negative. It depend upon situation.

What is cycle in graph? : Cycle graph or circular graph is collection of vertex and edges which create a loop.

What is Minimum spanning Tree? : Minimum spanning tree is subset of graph, Which is covered all vertices with minimum number of edges without create any cycles.

What is prim's algorithm ? : Prim's algorithm is an greedy algorithm, Which are used to find minimum spanning tree.

Given below mention solution of this problem using adjacency list..

``````import java.util.ArrayList;
/*
Java program for
*/
class Edge
{
// Source node
int u;
// Destination node
int v;
// Edge weight
int weight;
public Edge(int u, int v, int weight)
{
this.u = u;
this.v = v;
this.weight = weight;
}
}
class HeapNode
{
int vertex;
int key;
}
class ResultSet
{
int parent;
int weight;
}
class MinHeap
{
int capacity;
int currentSize;
HeapNode[] node;
int[] indexes;
public MinHeap(int capacity)
{
this.capacity = capacity;
node = new HeapNode[capacity + 1];
indexes = new int[capacity];
node[0] = new HeapNode();
node[0].key = Integer.MIN_VALUE;
node[0].vertex = -1;
currentSize = 0;
}
public void swap(int a, int b)
{
HeapNode temp = node[a];
node[a] = node[b];
node[b] = temp;
}
public boolean isEmpty()
{
return currentSize == 0;
}
public int heapSize()
{
return currentSize;
}
public void bubbleUp(int pos)
{
int parentIdx = pos / 2;
int currentIdx = pos;
while (currentIdx > 0
&& node[parentIdx].key > node[currentIdx].key)
{
HeapNode currentNode = node[currentIdx];
HeapNode parentNode = node[parentIdx];
indexes[currentNode.vertex] = parentIdx;
indexes[parentNode.vertex] = currentIdx;
swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
public void insert(HeapNode x)
{
currentSize++;
int idx = currentSize;
node[idx] = x;
indexes[x.vertex] = idx;
bubbleUp(idx);
}
public HeapNode extractMin()
{
HeapNode min = node[1];
HeapNode lastNode = node[currentSize];
indexes[lastNode.vertex] = 1;
node[1] = lastNode;
node[currentSize] = null;
sinkDown(1);
currentSize--;
return min;
}
public void sinkDown(int k)
{
int smallest = k;
// left child
int leftChild = 2 *k;
// right child
int rightChild = 2 *k + 1;
if (leftChild < heapSize()
&& node[smallest].key > node[leftChild].key)
{
smallest = leftChild;
}
if (rightChild < heapSize()
&& node[smallest].key > node[rightChild].key)
{
smallest = rightChild;
}
if (smallest != k)
{
HeapNode smallestNode = node[smallest];
HeapNode kNode = node[k];
indexes[smallestNode.vertex] = k;
indexes[kNode.vertex] = smallest;
swap(k, smallest);
sinkDown(smallest);
}
}
}
public class Graph
{
int vertices;
public ArrayList < ArrayList < Edge >> adjacencylist;
public Graph(int vertices)
{
this.vertices = vertices;
this.adjacencylist = new ArrayList < ArrayList < Edge >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v, int weight)
{
if (u == v)
{
// self loop
return;
}
}
public void decreaseKey(MinHeap minHeap, int newKey, int vertex)
{
int index = minHeap.indexes[vertex];
HeapNode node = minHeap.node[index];
node.key = newKey;
minHeap.bubbleUp(index);
}
public void primMST()
{
boolean[] inHeap = new boolean[this.vertices];
ResultSet[] resultSet = new ResultSet[this.vertices];
int[] key = new int[this.vertices];
HeapNode[] heapNodes = new HeapNode[this.vertices];
// Set default value of heap nodes resultset and keys
for (int i = 0; i < this.vertices; i++)
{
heapNodes[i] = new HeapNode();
heapNodes[i].vertex = i;
heapNodes[i].key = Integer.MAX_VALUE;
resultSet[i] = new ResultSet();
resultSet[i].parent = -1;
inHeap[i] = true;
key[i] = Integer.MAX_VALUE;
}
heapNodes[0].key = 0;
MinHeap minHeap = new MinHeap(this.vertices);
for (int j = 0; j < this.vertices; j++)
{
minHeap.insert(heapNodes[j]);
}
int i = 0;
while (minHeap.isEmpty() == false)
{
HeapNode extractedNode = minHeap.extractMin();
int extractedVertex = extractedNode.vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge.v])
{
int v = edge.v;
int w = edge.weight;
if (key[v] > w)
{
key[v] = w;
decreaseKey(minHeap, w, v);
resultSet[v].parent = extractedVertex;
resultSet[v].weight = w;
}
}
i++;
}
i = 0;
}
int result = 0;
System.out.print("\n\n Minimum Spanning Tree \n");
for (int node = 1; node < this.vertices; ++node)
{
System.out.println(" Edge (" + resultSet[node].parent +
"-" + node + ")  weight : " +
resultSet[node].weight);
result += resultSet[node].weight;
}
// Display calculated result
System.out.println(" Total minimum weight : " + result);
}
// Display graph nodes and edges
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
System.out.print(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adjacencylist.get(i).size(); ++j)
{
}
}
}
public static void main(String[] args)
{
Graph g = new Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````// Include header file
#include <iostream>
#include <limits.h>
#include <vector>

using namespace std;
/*
C++ program for
*/
class Edge
{
public:
// Source node
int u;
// Destination node
int v;
// Edge weight
int weight;
Edge(int u, int v, int weight)
{
this->u = u;
this->v = v;
this->weight = weight;
}
};
class HeapNode
{
public: int vertex;
int key;
};
class ResultSet
{
public: int parent;
int weight;
};
class MinHeap
{
public: int capacity;
int currentSize;
HeapNode **node;
int *indexes;
MinHeap(int capacity)
{
this->capacity = capacity;
this->node = new HeapNode*[capacity + 1];
this->indexes = new int[capacity];
this->node[0] = new HeapNode();
this->node[0]->key = INT_MIN;
this->node[0]->vertex = -1;
this->currentSize = 0;
}
void swap(int a, int b)
{
HeapNode *temp = this->node[a];
this->node[a] = this->node[b];
this->node[b] = temp;
}
bool isEmpty()
{
return this->currentSize == 0;
}
int heapSize()
{
return this->currentSize;
}
void bubbleUp(int pos)
{
int parentIdx = pos / 2;
int currentIdx = pos;
while (currentIdx > 0
&& this->node[parentIdx]->key > this->node[currentIdx]->key)
{
HeapNode *currentNode = this->node[currentIdx];
HeapNode *parentNode = this->node[parentIdx];
this->indexes[currentNode->vertex] = parentIdx;
this->indexes[parentNode->vertex] = currentIdx;
this->swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
void insert(HeapNode *x)
{
this->currentSize++;
int idx = this->currentSize;
this->node[idx] = x;
this->indexes[x->vertex] = idx;
this->bubbleUp(idx);
}
HeapNode *extractMin()
{
HeapNode *min = this->node[1];
HeapNode *lastNode = this->node[this->currentSize];
this->indexes[lastNode->vertex] = 1;
this->node[1] = lastNode;
this->node[this->currentSize] = NULL;
this->sinkDown(1);
this->currentSize--;
return min;
}
void sinkDown(int k)
{
int smallest = k;
// left child
int leftChild = 2 *k;
// right child
int rightChild = 2 *k + 1;
if (leftChild < this->heapSize()
&& this->node[smallest]->key > this->node[leftChild]->key)
{
smallest = leftChild;
}
if (rightChild < this->heapSize()
&& this->node[smallest]->key > this->node[rightChild]->key)
{
smallest = rightChild;
}
if (smallest != k)
{
HeapNode *smallestNode = this->node[smallest];
HeapNode *kNode = this->node[k];
this->indexes[smallestNode->vertex] = k;
this->indexes[kNode->vertex] = smallest;
this->swap(k, smallest);
this->sinkDown(smallest);
}
}
};
class Graph
{
public: int vertices;
vector < vector < Edge *> > adjacencylist;
Graph(int vertices)
{
this->vertices = vertices;
for (int i = 0; i < this->vertices; ++i)
{
this->adjacencylist.push_back( vector < Edge *> ());
}
}
void addEdge(int u, int v, int weight)
{
if (u == v)
{
// self loop
return;
}
}
void decreaseKey(MinHeap *minHeap, int newKey, int vertex)
{
int index = minHeap->indexes[vertex];
HeapNode *node = minHeap->node[index];
node->key = newKey;
minHeap->bubbleUp(index);
}
void primMST()
{
bool inHeap[this->vertices];
ResultSet *resultSet[this->vertices];
int key[this->vertices];
HeapNode *heapNodes[this->vertices];
// Set default value of heap nodes resultset and keys
for (int i = 0; i < this->vertices; i++)
{
heapNodes[i] = new HeapNode();
heapNodes[i]->vertex = i;
heapNodes[i]->key = INT_MAX;
resultSet[i] = new ResultSet();
resultSet[i]->parent = -1;
inHeap[i] = true;
key[i] = INT_MAX;
}
heapNodes[0]->key = 0;
MinHeap *minHeap = new MinHeap(this->vertices);
for (int j = 0; j < this->vertices; j++)
{
minHeap->insert(heapNodes[j]);
}
int i = 0;
while (minHeap->isEmpty() == false)
{
HeapNode *extractedNode = minHeap->extractMin();
int extractedVertex = extractedNode->vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge->v])
{
int v = edge->v;
int w = edge->weight;
if (key[v] > w)
{
key[v] = w;
this->decreaseKey(minHeap, w, v);
resultSet[v]->parent = extractedVertex;
resultSet[v]->weight = w;
}
}
i++;
}
i = 0;
}
int result = 0;
cout << "\n\n Minimum Spanning Tree \n";
for (int node = 1; node < this->vertices; ++node)
{
cout << " Edge (" << resultSet[node]->parent
<< "-" << node << ")  weight : "
<< resultSet[node]->weight << endl;
result += resultSet[node]->weight;
}
// Display calculated result
cout << " Total minimum weight : " << result << endl;
}
// Display graph nodes and edges
void printGraph()
{
cout << "\n Graph Adjacency List ";
for (int i = 0; i < this->vertices; ++i)
{
cout << " \n [" << i << "] :";
// iterate edges of i node
for (int j = 0; j < this->adjacencylist.at(i).size(); ++j)
{
cout << "  " << this->adjacencylist.at(i).at(j)->v;
}
}
}
};
int main()
{
Graph *g = new Graph(10);
// Display graph element
g->printGraph();
g->primMST();
return 0;
}``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
*/
public class Edge
{
// Source node
public int u;
// Destination node
public int v;
// Edge weight
public int weight;
public Edge(int u, int v, int weight)
{
this.u = u;
this.v = v;
this.weight = weight;
}
}
public class HeapNode
{
public int vertex;
public int key;
}
public class ResultSet
{
public int parent;
public int weight;
}
public class MinHeap
{
int capacity;
int currentSize;
public HeapNode[] node;
public int[] indexes;
public MinHeap(int capacity)
{
this.capacity = capacity;
this.node = new HeapNode[this.capacity + 1];
this.indexes = new int[this.capacity];
this.node[0] = new HeapNode();
this.node[0].key = int.MinValue;
this.node[0].vertex = -1;
this.currentSize = 0;
}
public void swap(int a, int b)
{
HeapNode temp = this.node[a];
this.node[a] = this.node[b];
this.node[b] = temp;
}
public Boolean isEmpty()
{
return this.currentSize == 0;
}
public int heapSize()
{
return this.currentSize;
}
public void bubbleUp(int pos)
{
int parentIdx = pos / 2;
int currentIdx = pos;
while (currentIdx > 0
&& this.node[parentIdx].key > this.node[currentIdx].key)
{
HeapNode currentNode = this.node[currentIdx];
HeapNode parentNode = this.node[parentIdx];
this.indexes[currentNode.vertex] = parentIdx;
this.indexes[parentNode.vertex] = currentIdx;
this.swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
public void insert(HeapNode x)
{
this.currentSize++;
int idx = this.currentSize;
this.node[idx] = x;
this.indexes[x.vertex] = idx;
this.bubbleUp(idx);
}
public HeapNode extractMin()
{
HeapNode min = this.node[1];
HeapNode lastNode = this.node[this.currentSize];
this.indexes[lastNode.vertex] = 1;
this.node[1] = lastNode;
this.node[this.currentSize] = null;
this.sinkDown(1);
this.currentSize--;
return min;
}
public void sinkDown(int k)
{
int smallest = k;
// left child
int leftChild = 2 * k;
// right child
int rightChild = 2 * k + 1;
if (leftChild < this.heapSize()
&& this.node[smallest].key > this.node[leftChild].key)
{
smallest = leftChild;
}
if (rightChild < this.heapSize()
&& this.node[smallest].key > this.node[rightChild].key)
{
smallest = rightChild;
}
if (smallest != k)
{
HeapNode smallestNode = this.node[smallest];
HeapNode kNode = this.node[k];
this.indexes[smallestNode.vertex] = k;
this.indexes[kNode.vertex] = smallest;
this.swap(k, smallest);
this.sinkDown(smallest);
}
}
}
public class Graph
{
int vertices;
public List < List < Edge >> adjacencylist;
public Graph(int vertices)
{
this.vertices = vertices;
this.adjacencylist = new List < List < Edge >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v, int weight)
{
if (u == v)
{
// self loop
return;
}
}
public void decreaseKey(MinHeap minHeap, int newKey, int vertex)
{
int index = minHeap.indexes[vertex];
HeapNode node = minHeap.node[index];
node.key = newKey;
minHeap.bubbleUp(index);
}
public void primMST()
{
Boolean[] inHeap = new Boolean[this.vertices];
ResultSet[] resultSet = new ResultSet[this.vertices];
int[] key = new int[this.vertices];
HeapNode[] heapNodes = new HeapNode[this.vertices];
// Set default value of heap nodes resultset and keys
for (int i = 0; i < this.vertices; i++)
{
heapNodes[i] = new HeapNode();
heapNodes[i].vertex = i;
heapNodes[i].key = int.MaxValue;
resultSet[i] = new ResultSet();
resultSet[i].parent = -1;
inHeap[i] = true;
key[i] = int.MaxValue;
}
heapNodes[0].key = 0;
MinHeap minHeap = new MinHeap(this.vertices);
for (int j = 0; j < this.vertices; j++)
{
minHeap.insert(heapNodes[j]);
}
int k = 0;
while (minHeap.isEmpty() == false)
{
HeapNode extractedNode = minHeap.extractMin();
int extractedVertex = extractedNode.vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge.v])
{
int v = edge.v;
int w = edge.weight;
if (key[v] > w)
{
key[v] = w;
this.decreaseKey(minHeap, w, v);
resultSet[v].parent = extractedVertex;
resultSet[v].weight = w;
}
}
k++;
}
k = 0;
}
int result = 0;
Console.Write("\n\n Minimum Spanning Tree \n");
for (int node = 1; node < this.vertices; ++node)
{
Console.WriteLine(" Edge (" + resultSet[node].parent +
"-" + node + ")  weight : " +
resultSet[node].weight);
result += resultSet[node].weight;
}
// Display calculated result
Console.WriteLine(" Total minimum weight : " + result);
}
// Display graph nodes and edges
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
Console.Write(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adjacencylist[i].Count; ++j)
{
}
}
}
public static void Main(String[] args)
{
Graph g = new Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````<?php
/*
Php program for
*/
class Edge
{
// Source node
public \$u;
// Destination node
public \$v;
// Edge weight
public \$weight;
public  function __construct(\$u, \$v, \$weight)
{
\$this->u = \$u;
\$this->v = \$v;
\$this->weight = \$weight;
}
}
class HeapNode
{
public \$vertex;
public \$key;
}
class ResultSet
{
public \$parent;
public \$weight;
}
class MinHeap
{
public \$capacity;
public \$currentSize;
public \$node;
public \$indexes;
public  function __construct(\$capacity)
{
\$this->capacity = \$capacity;
\$this->node = array_fill(0, \$capacity + 1, NULL);
\$this->indexes = array_fill(0, \$capacity, 0);
\$this->node[0] = new HeapNode();
\$this->node[0]->key = -PHP_INT_MAX;
\$this->node[0]->vertex = -1;
\$this->currentSize = 0;
}
public  function swap(\$a, \$b)
{
\$temp = \$this->node[\$a];
\$this->node[\$a] = \$this->node[\$b];
\$this->node[\$b] = \$temp;
}
public  function isEmpty()
{
return \$this->currentSize == 0;
}
public  function heapSize()
{
return \$this->currentSize;
}
public  function bubbleUp(\$pos)
{
\$parentIdx = (int)(\$pos / 2);
\$currentIdx = \$pos;
while (\$currentIdx > 0 && \$this->node[\$parentIdx]->key > \$this->node[\$currentIdx]->key)
{
\$currentNode = \$this->node[\$currentIdx];
\$parentNode = \$this->node[\$parentIdx];
\$this->indexes[\$currentNode->vertex] = \$parentIdx;
\$this->indexes[\$parentNode->vertex] = \$currentIdx;
\$this->swap(\$currentIdx, \$parentIdx);
\$currentIdx = \$parentIdx;
\$parentIdx = (int)(\$parentIdx / 2);
}
}
public  function insert(\$x)
{
\$this->currentSize++;
\$idx = \$this->currentSize;
\$this->node[\$idx] = \$x;
\$this->indexes[\$x->vertex] = \$idx;
\$this->bubbleUp(\$idx);
}
public  function extractMin()
{
\$min = \$this->node[1];
\$lastNode = \$this->node[\$this->currentSize];
\$this->indexes[\$lastNode->vertex] = 1;
\$this->node[1] = \$lastNode;
\$this->node[\$this->currentSize] = NULL;
\$this->sinkDown(1);
\$this->currentSize--;
return \$min;
}
public  function sinkDown(\$k)
{
\$smallest = \$k;
// left child
\$leftChild = 2 * \$k;
// right child
\$rightChild = 2 * \$k + 1;
if (\$leftChild < \$this->heapSize() && \$this->node[\$smallest]->key > \$this->node[\$leftChild]->key)
{
\$smallest = \$leftChild;
}
if (\$rightChild < \$this->heapSize() && \$this->node[\$smallest]->key > \$this->node[\$rightChild]->key)
{
\$smallest = \$rightChild;
}
if (\$smallest != \$k)
{
\$smallestNode = \$this->node[\$smallest];
\$kNode = \$this->node[\$k];
\$this->indexes[\$smallestNode->vertex] = \$k;
\$this->indexes[\$kNode->vertex] = \$smallest;
\$this->swap(\$k, \$smallest);
\$this->sinkDown(\$smallest);
}
}
}
class Graph
{
public \$vertices;
public  function __construct(\$vertices)
{
\$this->vertices = \$vertices;
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
}
}
{
\$this->adjacencylist[\$u][] = new Edge(\$u, \$v, \$weight);
if (\$u == \$v)
{
// self loop
return;
}
\$this->adjacencylist[\$v][] = new Edge(\$v, \$u, \$weight);
}
public  function decreaseKey(\$minHeap, \$newKey, \$vertex)
{
\$index = \$minHeap->indexes[\$vertex];
\$node = \$minHeap->node[\$index];
\$node->key = \$newKey;
\$minHeap->bubbleUp(\$index);
}
public  function primMST()
{
\$inHeap = array_fill(0, \$this->vertices, false);
\$resultSet = array_fill(0, \$this->vertices, NULL);
\$key = array_fill(0, \$this->vertices, 0);
\$heapNodes = array_fill(0, \$this->vertices, NULL);
// Set default value of heap nodes resultset and keys
for (\$i = 0; \$i < \$this->vertices; \$i++)
{
\$heapNodes[\$i] = new HeapNode();
\$heapNodes[\$i]->vertex = \$i;
\$heapNodes[\$i]->key = PHP_INT_MAX;
\$resultSet[\$i] = new ResultSet();
\$resultSet[\$i]->parent = -1;
\$inHeap[\$i] = true;
\$key[\$i] = PHP_INT_MAX;
}
\$heapNodes[0]->key = 0;
\$minHeap = new MinHeap(\$this->vertices);
for (\$j = 0; \$j < \$this->vertices; \$j++)
{
\$minHeap->insert(\$heapNodes[\$j]);
}
\$i = 0;
while (\$minHeap->isEmpty() == false)
{
\$extractedNode = \$minHeap->extractMin();
\$extractedVertex = \$extractedNode->vertex;
\$inHeap[\$extractedVertex] = false;
{
if (\$inHeap[\$edge->v])
{
\$v = \$edge->v;
\$w = \$edge->weight;
if (\$key[\$v] > \$w)
{
\$key[\$v] = \$w;
\$this->decreaseKey(\$minHeap, \$w, \$v);
\$resultSet[\$v]->parent = \$extractedVertex;
\$resultSet[\$v]->weight = \$w;
}
}
\$i++;
}
\$i = 0;
}
\$result = 0;
echo("\n\n Minimum Spanning Tree \n");
for (\$node = 1; \$node < \$this->vertices; ++\$node)
{
echo(" Edge (".\$resultSet[\$node]->parent.
"-".\$node.
")  weight : ".\$resultSet[\$node]->weight.
"\n");
\$result += \$resultSet[\$node]->weight;
}
// Display calculated result
echo(" Total minimum weight : ".\$result.
"\n");
}
// Display graph nodes and edges
public  function printGraph()
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
echo(" \n [".\$i."] :");
// iterate edges of i node
for (\$j = 0; \$j < count(\$this->adjacencylist[\$i]); ++\$j)
{
}
}
}
}

function main()
{
\$g = new Graph(10);
// Display graph element
\$g->printGraph();
\$g->primMST();
}
main();``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````/*
Node JS program for
*/
class Edge
{
constructor(u, v, weight)
{
this.u = u;
this.v = v;
this.weight = weight;
}
}
class HeapNode
{
constructor()
{
this.vertex = 0;
this.key = 0;
}
}
class ResultSet
{
constructor()
{
this.parent = 0;
this.weight = 0;
}
}
class MinHeap
{
constructor(capacity)
{
this.capacity = capacity;
this.node = Array(capacity + 1).fill(null);
this.indexes = Array(capacity).fill(0);
this.node[0] = new HeapNode();
this.node[0].key = -Number.MAX_VALUE;
this.node[0].vertex = -1;
this.currentSize = 0;
}
swap(a, b)
{
var temp = this.node[a];
this.node[a] = this.node[b];
this.node[b] = temp;
}
isEmpty()
{
return this.currentSize == 0;
}
heapSize()
{
return this.currentSize;
}
bubbleUp(pos)
{
var parentIdx = parseInt(pos / 2);
var currentIdx = pos;
while (currentIdx > 0
&& this.node[parentIdx].key > this.node[currentIdx].key)
{
var currentNode = this.node[currentIdx];
var parentNode = this.node[parentIdx];
this.indexes[currentNode.vertex] = parentIdx;
this.indexes[parentNode.vertex] = currentIdx;
this.swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parseInt(parentIdx / 2);
}
}
insert(x)
{
this.currentSize++;
var idx = this.currentSize;
this.node[idx] = x;
this.indexes[x.vertex] = idx;
this.bubbleUp(idx);
}
extractMin()
{
var min = this.node[1];
var lastNode = this.node[this.currentSize];
this.indexes[lastNode.vertex] = 1;
this.node[1] = lastNode;
this.node[this.currentSize] = null;
this.sinkDown(1);
this.currentSize--;
return min;
}
sinkDown(k)
{
var smallest = k;
// left child
var leftChild = 2 * k;
// right child
var rightChild = 2 * k + 1;
if (leftChild < this.heapSize()
&& this.node[smallest].key > this.node[leftChild].key)
{
smallest = leftChild;
}
if (rightChild < this.heapSize()
&& this.node[smallest].key > this.node[rightChild].key)
{
smallest = rightChild;
}
if (smallest != k)
{
var smallestNode = this.node[smallest];
var kNode = this.node[k];
this.indexes[smallestNode.vertex] = k;
this.indexes[kNode.vertex] = smallest;
this.swap(k, smallest);
this.sinkDown(smallest);
}
}
}
class Graph
{
constructor(vertices)
{
this.vertices = vertices;
for (var i = 0; i < this.vertices; ++i)
{
}
}
{
if (u == v)
{
// self loop
return;
}
}
decreaseKey(minHeap, newKey, vertex)
{
var index = minHeap.indexes[vertex];
var node = minHeap.node[index];
node.key = newKey;
minHeap.bubbleUp(index);
}
primMST()
{
var inHeap = Array(this.vertices).fill(false);
var resultSet = Array(this.vertices).fill(null);
var key = Array(this.vertices).fill(0);
var heapNodes = Array(this.vertices).fill(null);
// Set default value of heap nodes resultset and keys
for (var i = 0; i < this.vertices; i++)
{
heapNodes[i] = new HeapNode();
heapNodes[i].vertex = i;
heapNodes[i].key = Number.MAX_VALUE;
resultSet[i] = new ResultSet();
resultSet[i].parent = -1;
inHeap[i] = true;
key[i] = Number.MAX_VALUE;
}
heapNodes[0].key = 0;
var minHeap = new MinHeap(this.vertices);
for (var j = 0; j < this.vertices; j++)
{
minHeap.insert(heapNodes[j]);
}
var i = 0;
while (minHeap.isEmpty() == false)
{
var extractedNode = minHeap.extractMin();
var extractedVertex = extractedNode.vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge.v])
{
var v = edge.v;
var w = edge.weight;
if (key[v] > w)
{
key[v] = w;
this.decreaseKey(minHeap, w, v);
resultSet[v].parent = extractedVertex;
resultSet[v].weight = w;
}
}
i++;
}
i = 0;
}
var result = 0;
process.stdout.write("\n\n Minimum Spanning Tree \n");
for (var node = 1; node < this.vertices; ++node)
{
console.log(" Edge (" + resultSet[node].parent +
"-" + node + ")  weight : " + resultSet[node].weight);
result += resultSet[node].weight;
}
// Display calculated result
console.log(" Total minimum weight : " + result);
}
// Display graph nodes and edges
printGraph()
{
for (var i = 0; i < this.vertices; ++i)
{
process.stdout.write(" \n [" + i + "] :");
// iterate edges of i node
for (var j = 0; j < this.adjacencylist[i].length; ++j)
{
}
}
}
}

function main()
{
var g = new Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}
main();``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````import sys
#    Python 3 program for
#    Prim's algorithm using adjacency list
class Edge :
#  Source node
#  Destination node
#  Edge weight
def __init__(self, u, v, weight) :
self.u = u
self.v = v
self.weight = weight

class HeapNode :
def __init__(self) :
self.vertex = 0
self.key = 0

class ResultSet :
def __init__(self) :
self.parent = 0
self.weight = 0

class MinHeap :
def __init__(self, capacity) :
self.capacity = capacity
self.node = [None] * (capacity + 1)
self.indexes = [0] * (capacity)
self.node[0] = HeapNode()
self.node[0].key = -sys.maxsize
self.node[0].vertex = -1
self.currentSize = 0

def swap(self, a, b) :
temp = self.node[a]
self.node[a] = self.node[b]
self.node[b] = temp

def isEmpty(self) :
return self.currentSize == 0

def heapSize(self) :
return self.currentSize

def bubbleUp(self, pos) :
parentIdx = int(pos / 2)
currentIdx = pos
while (currentIdx > 0 and
self.node[parentIdx].key > self.node[currentIdx].key) :
currentNode = self.node[currentIdx]
parentNode = self.node[parentIdx]
self.indexes[currentNode.vertex] = parentIdx
self.indexes[parentNode.vertex] = currentIdx
self.swap(currentIdx, parentIdx)
currentIdx = parentIdx
parentIdx = int(parentIdx / 2)

def insert(self, x) :
self.currentSize += 1
idx = self.currentSize
self.node[idx] = x
self.indexes[x.vertex] = idx
self.bubbleUp(idx)

def extractMin(self) :
min = self.node[1]
lastNode = self.node[self.currentSize]
self.indexes[lastNode.vertex] = 1
self.node[1] = lastNode
self.node[self.currentSize] = None
self.sinkDown(1)
self.currentSize -= 1
return min

def sinkDown(self, k) :
smallest = k
#  left child
leftChild = 2 * k
#  right child
rightChild = 2 * k + 1
if (leftChild < self.heapSize() and
self.node[smallest].key > self.node[leftChild].key) :
smallest = leftChild

if (rightChild < self.heapSize() and
self.node[smallest].key > self.node[rightChild].key) :
smallest = rightChild

if (smallest != k) :
smallestNode = self.node[smallest]
kNode = self.node[k]
self.indexes[smallestNode.vertex] = k
self.indexes[kNode.vertex] = smallest
self.swap(k, smallest)
self.sinkDown(smallest)

class Graph :
def __init__(self, vertices) :
self.vertices = vertices
i = 0
while (i < self.vertices) :
i += 1

def addEdge(self, u, v, weight) :
if (u == v) :
#  self loop
return

def decreaseKey(self, minHeap, newKey, vertex) :
index = minHeap.indexes[vertex]
node = minHeap.node[index]
node.key = newKey
minHeap.bubbleUp(index)

def primMST(self) :
inHeap = [False] * (self.vertices)
resultSet = [None] * (self.vertices)
key = [0] * (self.vertices)
heapNodes = [None] * (self.vertices)
i = 0
#  Set default value of heap nodes resultset and keys
while (i < self.vertices) :
heapNodes[i] = HeapNode()
heapNodes[i].vertex = i
heapNodes[i].key = sys.maxsize
resultSet[i] = ResultSet()
resultSet[i].parent = -1
inHeap[i] = True
key[i] = sys.maxsize
i += 1

heapNodes[0].key = 0
minHeap = MinHeap(self.vertices)
j = 0
while (j < self.vertices) :
minHeap.insert(heapNodes[j])
j += 1

i = 0
while (minHeap.isEmpty() == False) :
extractedNode = minHeap.extractMin()
extractedVertex = extractedNode.vertex
inHeap[extractedVertex] = False
if (inHeap[edge.v]) :
v = edge.v
w = edge.weight
if (key[v] > w) :
key[v] = w
self.decreaseKey(minHeap, w, v)
resultSet[v].parent = extractedVertex
resultSet[v].weight = w

i += 1

i = 0

result = 0
print("\n\n Minimum Spanning Tree ")
node = 1
while (node < self.vertices) :
print(" Edge (", resultSet[node].parent ,"-", node ,
")  weight : ", resultSet[node].weight)
result += resultSet[node].weight
node += 1

#  Display calculated result
print(" Total minimum weight : ", result)

#  Display graph nodes and edges
def printGraph(self) :
print("\n Graph Adjacency List ", end = "")
i = 0
while (i < self.vertices) :
print(" \n [", i ,"] :", end = "")
j = 0
#  iterate edges of i node
print("  ", self.adjacencylist[i][j].v, end = "")
j += 1

i += 1

def main() :
g = Graph(10)
#  Display graph element
g.printGraph()
g.primMST()

if __name__ == "__main__": main()``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   7   8
[ 1 ] :   0   2   8
[ 2 ] :   1   3   6   9
[ 3 ] :   2   4   9
[ 4 ] :   3   5
[ 5 ] :   4   6   9
[ 6 ] :   2   5   7   8
[ 7 ] :   0   6
[ 8 ] :   0   1   6   9
[ 9 ] :   2   3   5   8

Minimum Spanning Tree
Edge ( 8 - 1 )  weight :  6
Edge ( 3 - 2 )  weight :  8
Edge ( 9 - 3 )  weight :  5
Edge ( 5 - 4 )  weight :  15
Edge ( 9 - 5 )  weight :  7
Edge ( 7 - 6 )  weight :  2
Edge ( 0 - 7 )  weight :  6
Edge ( 0 - 8 )  weight :  4
Edge ( 8 - 9 )  weight :  3
Total minimum weight :  56``````
``````#    Ruby program for
#    Prim's algorithm using adjacency list
class Edge
# Define the accessor and reader of class Edge
attr_accessor :u, :v, :weight
#  Source node
#  Destination node
#  Edge weight
def initialize(u, v, weight)
self.u = u
self.v = v
self.weight = weight
end

end

class HeapNode
# Define the accessor and reader of class HeapNode
attr_accessor :vertex, :key
def initialize()
self.vertex = 0
self.key = 0
end

end

class ResultSet
# Define the accessor and reader of class ResultSet
attr_accessor :parent, :weight
def initialize()
self.parent = 0
self.weight = 0
end

end

class MinHeap
# Define the accessor and reader of class MinHeap
attr_accessor :capacity, :currentSize, :node, :indexes
def initialize(capacity)
self.capacity = capacity
self.node = Array.new(capacity + 1) {nil}
self.indexes = Array.new(capacity) {0}
self.node[0] = HeapNode.new()
self.node[0].key = -(2 ** (0. size * 8 - 2))
self.node[0].vertex = -1
self.currentSize = 0
end

def swap(a, b)
temp = self.node[a]
self.node[a] = self.node[b]
self.node[b] = temp
end

def isEmpty()
return self.currentSize == 0
end

def heapSize()
return self.currentSize
end

def bubbleUp(pos)
parentIdx = pos / 2
currentIdx = pos
while (currentIdx > 0 &&
self.node[parentIdx].key > self.node[currentIdx].key)
currentNode = self.node[currentIdx]
parentNode = self.node[parentIdx]
self.indexes[currentNode.vertex] = parentIdx
self.indexes[parentNode.vertex] = currentIdx
self.swap(currentIdx, parentIdx)
currentIdx = parentIdx
parentIdx = parentIdx / 2
end

end

def insert(x)
self.currentSize += 1
idx = self.currentSize
self.node[idx] = x
self.indexes[x.vertex] = idx
self.bubbleUp(idx)
end

def extractMin()
min = self.node[1]
lastNode = self.node[self.currentSize]
self.indexes[lastNode.vertex] = 1
self.node[1] = lastNode
self.node[self.currentSize] = nil
self.sinkDown(1)
self.currentSize -= 1
return min
end

def sinkDown(k)
smallest = k
#  left child
leftChild = 2 * k
#  right child
rightChild = 2 * k + 1
if (leftChild < self.heapSize() &&
self.node[smallest].key > self.node[leftChild].key)
smallest = leftChild
end

if (rightChild < self.heapSize() &&
self.node[smallest].key > self.node[rightChild].key)
smallest = rightChild
end

if (smallest != k)
smallestNode = self.node[smallest]
kNode = self.node[k]
self.indexes[smallestNode.vertex] = k
self.indexes[kNode.vertex] = smallest
self.swap(k, smallest)
self.sinkDown(smallest)
end

end

end

class Graph
# Define the accessor and reader of class Graph
def initialize(vertices)
self.vertices = vertices
i = 0
while (i < self.vertices)
i += 1
end

end

if (u == v)
#  self loop
return
end

end

def decreaseKey(minHeap, newKey, vertex)
index = minHeap.indexes[vertex]
node = minHeap.node[index]
node.key = newKey
minHeap.bubbleUp(index)
end

def primMST()
inHeap = Array.new(self.vertices) {false}
resultSet = Array.new(self.vertices) {nil}
key = Array.new(self.vertices) {0}
heapNodes = Array.new(self.vertices) {nil}
i = 0
#  Set default value of heap nodes resultset and keys
while (i < self.vertices)
heapNodes[i] = HeapNode.new()
heapNodes[i].vertex = i
heapNodes[i].key = (2 ** (0. size * 8 - 2))
resultSet[i] = ResultSet.new()
resultSet[i].parent = -1
inHeap[i] = true
key[i] = (2 ** (0. size * 8 - 2))
i += 1
end

heapNodes[0].key = 0
minHeap = MinHeap.new(self.vertices)
j = 0
while (j < self.vertices)
minHeap.insert(heapNodes[j])
j += 1
end

i = 0
while (minHeap.isEmpty() == false)
extractedNode = minHeap.extractMin()
extractedVertex = extractedNode.vertex
inHeap[extractedVertex] = false
if (inHeap[edge.v])
v = edge.v
w = edge.weight
if (key[v] > w)
key[v] = w
self.decreaseKey(minHeap, w, v)
resultSet[v].parent = extractedVertex
resultSet[v].weight = w
end

end

i += 1
end

i = 0
end

result = 0
print("\n\n Minimum Spanning Tree \n")
node = 1
while (node < self.vertices)
print(" Edge (", resultSet[node].parent ,"-",
node ,")  weight : ", resultSet[node].weight, "\n")
result += resultSet[node].weight
node += 1
end

#  Display calculated result
print(" Total minimum weight : ", result, "\n")
end

#  Display graph nodes and edges
def printGraph()
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
#  iterate edges of i node
j += 1
end

i += 1
end

end

end

def main()
g = Graph.new(10)
#  Display graph element
g.printGraph()
g.primMST()
end

main()``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56
``````
``````import scala.collection.mutable._;
/*
Scala program for
*/
class Edge(
// Source node
var u: Int,
// Destination node
var v: Int,
// Edge weight
var weight: Int)
{}
class HeapNode(var vertex: Int,
var key: Int)
{
def this()
{
this(0,0);
}
}
class ResultSet(var parent: Int,
var weight: Int)
{
def this()
{
this(0,0);
}
}
class MinHeap(var capacity: Int,
var currentSize: Int,
var node: Array[HeapNode],
var indexes: Array[Int])
{
def this(capacity: Int)
{
this(capacity,0,Array.fill[HeapNode](capacity + 1)(null),Array.fill[Int](capacity)(0));
node(0) = new HeapNode();
node(0).key = Int.MinValue;
node(0).vertex = -1;

}
def swap(a: Int, b: Int): Unit = {
var temp: HeapNode = node(a);
node(a) = node(b);
node(b) = temp;
}
def isEmpty(): Boolean = {
return currentSize == 0;
}
def heapSize(): Int = {
return currentSize;
}
def bubbleUp(pos: Int): Unit = {
var parentIdx: Int = pos / 2;
var currentIdx: Int = pos;
while (currentIdx > 0 && node(parentIdx).key > node(currentIdx).key)
{
var currentNode: HeapNode = node(currentIdx);
var parentNode: HeapNode = node(parentIdx);
indexes(currentNode.vertex) = parentIdx;
indexes(parentNode.vertex) = currentIdx;
swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
def insert(x: HeapNode): Unit = {
currentSize += 1;
var idx: Int = currentSize;
node(idx) = x;
indexes(x.vertex) = idx;
bubbleUp(idx);
}
def extractMin(): HeapNode = {
var min: HeapNode = node(1);
var lastNode: HeapNode = node(currentSize);
indexes(lastNode.vertex) = 1;
node(1) = lastNode;
node(currentSize) = null;
sinkDown(1);
currentSize -= 1;
return min;
}
def sinkDown(k: Int): Unit = {
var smallest: Int = k;
// left child
var leftChild: Int = 2 * k;
// right child
var rightChild: Int = 2 * k + 1;
if (leftChild < heapSize() && node(smallest).key > node(leftChild).key)
{
smallest = leftChild;
}
if (rightChild < heapSize() && node(smallest).key > node(rightChild).key)
{
smallest = rightChild;
}
if (smallest != k)
{
var smallestNode: HeapNode = node(smallest);
var kNode: HeapNode = node(k);
indexes(smallestNode.vertex) = k;
indexes(kNode.vertex) = smallest;
swap(k, smallest);
sinkDown(smallest);
}
}
}
class Graph(var vertices: Int,
{
def this(vertices: Int)
{
this(vertices,new ArrayBuffer[ArrayBuffer[Edge]](vertices));
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
def addEdge(u: Int, v: Int, weight: Int): Unit = {
adjacencylist(u) += new Edge(u, v, weight);
if (u == v)
{
// self loop
return;
}
adjacencylist(v) += new Edge(v, u, weight);
}
def decreaseKey(minHeap: MinHeap, newKey: Int, vertex: Int): Unit = {
var index: Int = minHeap.indexes(vertex);
var node: HeapNode = minHeap.node(index);
node.key = newKey;
minHeap.bubbleUp(index);
}
def primMST(): Unit = {
var inHeap: Array[Boolean] = Array.fill[Boolean](this.vertices)(false);
var resultSet: Array[ResultSet] = Array.fill[ResultSet](this.vertices)(null);
var key: Array[Int] = Array.fill[Int](this.vertices)(0);
var heapNodes: Array[HeapNode] = Array.fill[HeapNode](this.vertices)(null);
var i: Int = 0;
// Set default value of heap nodes resultset and keys
while (i < this.vertices)
{
heapNodes(i) = new HeapNode();
heapNodes(i).vertex = i;
heapNodes(i).key = Int.MaxValue;
resultSet(i) = new ResultSet();
resultSet(i).parent = -1;
inHeap(i) = true;
key(i) = Int.MaxValue;
i += 1;
}
heapNodes(0).key = 0;
var minHeap: MinHeap = new MinHeap(this.vertices);
var j: Int = 0;
while (j < this.vertices)
{
minHeap.insert(heapNodes(j));
j += 1;
}
i = 0;
while (minHeap.isEmpty() == false)
{
var extractedNode: HeapNode = minHeap.extractMin();
var extractedVertex: Int = extractedNode.vertex;
inHeap(extractedVertex) = false;
{
if (inHeap(edge.v))
{
var v: Int = edge.v;
var w: Int = edge.weight;
if (key(v) > w)
{
key(v) = w;
decreaseKey(minHeap, w, v);
resultSet(v).parent = extractedVertex;
resultSet(v).weight = w;
}
}
i += 1;
}
i = 0;
}
var result: Int = 0;
print("\n\n Minimum Spanning Tree \n");
var node: Int = 1;
while (node < this.vertices)
{
println(" Edge (" + resultSet(node).parent + "-" + node + ")  weight : " + resultSet(node).weight);
result += resultSet(node).weight;
node += 1;
}
// Display calculated result
println(" Total minimum weight : " + result);
}
// Display graph nodes and edges
def printGraph(): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var g: Graph = new Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````import Foundation;
/*
Swift 4 program for
*/
class Edge
{
// Source node
var u: Int;
// Destination node
var v: Int;
// Edge weight
var weight: Int;
init(_ u: Int, _ v: Int, _ weight: Int)
{
self.u = u;
self.v = v;
self.weight = weight;
}
}
class HeapNode
{
var vertex: Int;
var key: Int;
init()
{
self.vertex = 0;
self.key = 0;
}
}
class ResultSet
{
var parent: Int;
var weight: Int;
init()
{
self.parent = 0;
self.weight = 0;
}
}
class MinHeap
{
var capacity: Int;
var currentSize: Int;
var node: [HeapNode? ];
var indexes: [Int];
init(_ capacity: Int)
{
self.capacity = capacity;
self.node = Array(repeating: nil, count: capacity + 1);
self.indexes = Array(repeating: 0, count: capacity);
self.node[0] = HeapNode();
self.node[0]!.key = Int.min;
self.node[0]!.vertex = -1;
self.currentSize = 0;
}
func swap(_ a: Int, _ b: Int)
{
let temp: HeapNode? = self.node[a];
self.node[a] = self.node[b];
self.node[b] = temp;
}
func isEmpty() -> Bool
{
return self.currentSize == 0;
}
func heapSize() -> Int
{
return self.currentSize;
}
func bubbleUp(_ pos: Int)
{
var parentIdx: Int = pos / 2;
var currentIdx: Int = pos;
while (currentIdx > 0
&& self.node[parentIdx]!.key > self.node[currentIdx]!.key)
{
let currentNode: HeapNode? = self.node[currentIdx];
let parentNode: HeapNode? = self.node[parentIdx];
self.indexes[currentNode!.vertex] = parentIdx;
self.indexes[parentNode!.vertex] = currentIdx;
self.swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
func insert(_ x: HeapNode? )
{
self.currentSize += 1;
let idx: Int = self.currentSize;
self.node[idx] = x;
self.indexes[x!.vertex] = idx;
self.bubbleUp(idx);
}
func extractMin() -> HeapNode?
{
let min: HeapNode? = self.node[1];
let lastNode: HeapNode? = self.node[self.currentSize];
self.indexes[lastNode!.vertex] = 1;
self.node[1] = lastNode;
self.node[self.currentSize] = nil;
self.sinkDown(1);
self.currentSize -= 1;
return min;
}
func sinkDown(_ k: Int)
{
var smallest: Int = k;
// left child
let leftChild: Int = 2 * k;
// right child
let rightChild: Int = 2 * k + 1;
if (leftChild < self.heapSize()
&& self.node[smallest]!.key > self.node[leftChild]!.key)
{
smallest = leftChild;
}
if (rightChild < self.heapSize()
&& self.node[smallest]!.key > self.node[rightChild]!.key)
{
smallest = rightChild;
}
if (smallest  != k)
{
let smallestNode: HeapNode? = self.node[smallest];
let kNode: HeapNode? = self.node[k];
self.indexes[smallestNode!.vertex] = k;
self.indexes[kNode!.vertex] = smallest;
self.swap(k, smallest);
self.sinkDown(smallest);
}
}
}
class Graph
{
var vertices: Int;
[Edge?]
];
init(_ vertices: Int)
{
self.vertices = vertices;
var i: Int = 0;
while (i < self.vertices)
{
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int, _ weight: Int)
{
if (u == v)
{
// self loop
return;
}
}
func decreaseKey(_ minHeap: MinHeap? , _ newKey : Int, _ vertex: Int)
{
let index: Int = minHeap!.indexes[vertex];
let node: HeapNode? = minHeap!.node[index];
node!.key = newKey;
minHeap!.bubbleUp(index);
}
func primMST()
{
var inHeap: [Bool] =
Array(repeating: false, count: self.vertices);
var resultSet: [ResultSet? ] =
Array(repeating: nil, count: self.vertices);
var key: [Int] =
Array(repeating: 0, count: self.vertices);
var heapNodes: [HeapNode? ] =
Array(repeating: nil, count: self.vertices);
var i: Int = 0;
// Set default value of heap nodes resultset and keys
while (i < self.vertices)
{
heapNodes[i] = HeapNode();
heapNodes[i]!.vertex = i;
heapNodes[i]!.key = Int.max;
resultSet[i] = ResultSet();
resultSet[i]!.parent = -1;
inHeap[i] = true;
key[i] = Int.max;
i += 1;
}
heapNodes[0]!.key = 0;
let minHeap: MinHeap? = MinHeap(self.vertices);
var j: Int = 0;
while (j < self.vertices)
{
minHeap!.insert(heapNodes[j]);
j += 1;
}
i = 0;
while (minHeap!.isEmpty() == false)
{
let extractedNode: HeapNode? = minHeap!.extractMin();
let extractedVertex: Int = extractedNode!.vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge!.v])
{
let v: Int = edge!.v;
let w: Int = edge!.weight;
if (key[v] > w)
{
key[v] = w;
self.decreaseKey(minHeap, w, v);
resultSet[v]!.parent = extractedVertex;
resultSet[v]!.weight = w;
}
}
i += 1;
}
i = 0;
}
var result: Int = 0;
print("\n\n Minimum Spanning Tree ");
var node: Int = 1;
while (node < self.vertices)
{
print(" Edge (", resultSet[node]!.parent ,"-",
node ,")  weight : ", resultSet[node]!.weight);
result += resultSet[node]!.weight;
node += 1;
}
// Display calculated result
print(" Total minimum weight : ", result);
}
// Display graph nodes and edges
func printGraph()
{
print("\n Graph Adjacency List ", terminator: "");
var i: Int = 0;
while (i < self.vertices)
{
print(" \n [", i ,"] :", terminator: "");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
}
func main()
{
let g: Graph = Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}
main();``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   7   8
[ 1 ] :   0   2   8
[ 2 ] :   1   3   6   9
[ 3 ] :   2   4   9
[ 4 ] :   3   5
[ 5 ] :   4   6   9
[ 6 ] :   2   5   7   8
[ 7 ] :   0   6
[ 8 ] :   0   1   6   9
[ 9 ] :   2   3   5   8

Minimum Spanning Tree
Edge ( 8 - 1 )  weight :  6
Edge ( 3 - 2 )  weight :  8
Edge ( 9 - 3 )  weight :  5
Edge ( 5 - 4 )  weight :  15
Edge ( 9 - 5 )  weight :  7
Edge ( 7 - 6 )  weight :  2
Edge ( 0 - 7 )  weight :  6
Edge ( 0 - 8 )  weight :  4
Edge ( 8 - 9 )  weight :  3
Total minimum weight :  56``````
``````/*
Kotlin program for
*/
class Edge
{
// Source node
var u: Int;
// Destination node
var v: Int;
// Edge weight
var weight: Int;
constructor(u: Int, v: Int, weight: Int)
{
this.u = u;
this.v = v;
this.weight = weight;
}
}
class HeapNode
{
var vertex: Int;
var key: Int;
constructor()
{
this.vertex = 0;
this.key = 0;
}
}
class ResultSet
{
var parent: Int;
var weight: Int;
constructor()
{
this.parent = 0;
this.weight = 0;
}
}
class MinHeap
{
var capacity: Int;
var currentSize: Int;
var node: Array < HeapNode ? > ;
var indexes: Array < Int > ;
constructor(capacity: Int)
{
this.capacity = capacity;
this.node = Array(capacity + 1)
{
null
};
this.indexes = Array(capacity)
{
0
};
this.node[0] = HeapNode();
this.node[0]!!.key = Int.MIN_VALUE;
this.node[0]!!.vertex = -1;
this.currentSize = 0;
}
fun swap(a: Int, b: Int): Unit
{
val temp: HeapNode? = this.node[a];
this.node[a] = this.node[b];
this.node[b] = temp;
}
fun isEmpty(): Boolean
{
return this.currentSize == 0;
}
fun heapSize(): Int
{
return this.currentSize;
}
fun bubbleUp(pos: Int): Unit
{
var parentIdx: Int = pos / 2;
var currentIdx: Int = pos;
while (currentIdx > 0
&& this.node[parentIdx]!!.key > this.node[currentIdx]!!.key)
{
val currentNode: HeapNode? = this.node[currentIdx];
val parentNode: HeapNode? = this.node[parentIdx];
this.indexes[currentNode!!.vertex] = parentIdx;
this.indexes[parentNode!!.vertex] = currentIdx;
this.swap(currentIdx, parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx / 2;
}
}
fun insert(x: HeapNode ? ): Unit
{
this.currentSize += 1;
val idx: Int = this.currentSize;
this.node[idx] = x;
this.indexes[x!!.vertex] = idx;
this.bubbleUp(idx);
}
fun extractMin(): HeapNode ?
{
val min: HeapNode? = this.node[1];
val lastNode: HeapNode? = this.node[this.currentSize];
this.indexes[lastNode!!.vertex] = 1;
this.node[1] = lastNode;
this.node[this.currentSize] = null;
this.sinkDown(1);
this.currentSize -= 1;
return min;
}
fun sinkDown(k: Int): Unit
{
var smallest: Int = k;
// left child
val leftChild: Int = 2 * k;
// right child
val rightChild: Int = 2 * k + 1;
if (leftChild < this.heapSize() && this.node[smallest]!!.key > this.node[leftChild]!!.key)
{
smallest = leftChild;
}
if (rightChild < this.heapSize() && this.node[smallest]!!.key > this.node[rightChild]!!.key)
{
smallest = rightChild;
}
if (smallest != k)
{
val smallestNode: HeapNode? = this.node[smallest];
val kNode: HeapNode? = this.node[k];
this.indexes[smallestNode!!.vertex] = k;
this.indexes[kNode!!.vertex] = smallest;
this.swap(k, smallest);
this.sinkDown(smallest);
}
}
}
class Graph
{
var vertices: Int;
var adjacencylist: MutableList < MutableList < Edge >> ;
constructor(vertices: Int)
{
this.vertices = vertices;
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
fun addEdge(u: Int, v: Int, weight: Int): Unit
{
if (u == v)
{
// self loop
return;
}
}
fun decreaseKey(minHeap: MinHeap ? , newKey : Int, vertex: Int): Unit
{
val index: Int = minHeap!!.indexes[vertex];
var node: HeapNode ? = minHeap.node[index];
node!!.key = newKey;
minHeap.bubbleUp(index);
}
fun primMST(): Unit
{
val inHeap: Array < Boolean > = Array(this.vertices)
{
false
};
val resultSet: Array < ResultSet ? > = Array(this.vertices)
{
null
};
val key: Array < Int > = Array(this.vertices)
{
0
};
val heapNodes: Array < HeapNode ? > = Array(this.vertices)
{
null
};
var i: Int = 0;
// Set default value of heap nodes resultset and keys
while (i < this.vertices)
{
heapNodes[i] = HeapNode();
heapNodes[i]!!.vertex = i;
heapNodes[i]!!.key = Int.MAX_VALUE;
resultSet[i] = ResultSet();
resultSet[i]!!.parent = -1;
inHeap[i] = true;
key[i] = Int.MAX_VALUE;
i += 1;
}
heapNodes[0]?.key = 0;
val minHeap: MinHeap = MinHeap(this.vertices);
var j: Int = 0;
while (j < this.vertices)
{
minHeap.insert(heapNodes[j]);
j += 1;
}
i = 0;
while (minHeap.isEmpty() == false)
{
val extractedNode: HeapNode? = minHeap.extractMin();
val extractedVertex: Int = extractedNode!!.vertex;
inHeap[extractedVertex] = false;
{
if (inHeap[edge!!.v])
{
val v: Int = edge.v;
val w: Int = edge.weight;
if (key[v] > w)
{
key[v] = w;
this.decreaseKey(minHeap, w, v);
resultSet[v]!!.parent = extractedVertex;
resultSet[v]!!.weight = w;
}
}
i += 1;
}
i = 0;
}
var result: Int = 0;
print("\n\n Minimum Spanning Tree \n");
var node: Int = 1;
while (node < this.vertices)
{
println(" Edge (" + resultSet[node]!!.parent + "-" + node + ")  weight : " + resultSet[node]!!.weight);
result += resultSet[node]!!.weight;
node += 1;
}
// Display calculated result
println(" Total minimum weight : " + result);
}
// Display graph nodes and edges
fun printGraph(): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val g: Graph = Graph(10);
// Display graph element
g.printGraph();
g.primMST();
}``````

#### input

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge (8-1)  weight : 6
Edge (3-2)  weight : 8
Edge (9-3)  weight : 5
Edge (5-4)  weight : 15
Edge (9-5)  weight : 7
Edge (7-6)  weight : 2
Edge (0-7)  weight : 6
Edge (0-8)  weight : 4
Edge (8-9)  weight : 3
Total minimum weight : 56``````
``````package main
import "math"
import "fmt"
/*
Go program for
*/
type Edge struct {

u int // Source node
v int // Destination node
weight int // Edge weight

}
func getEdge(u int, v int, weight int) * Edge {
var me *Edge = &Edge {u,v,weight}
return me
}
type HeapNode struct {
vertex int
key int
}
func getHeapNode() * HeapNode {
var me *HeapNode = &HeapNode {}
return me
}
type ResultSet struct {
parent int
weight int
}
func getResultSet() * ResultSet {
var me *ResultSet = &ResultSet {}
return me
}
type MinHeap struct {
capacity int
currentSize int
node []* HeapNode
indexes []int
}
func getMinHeap(capacity int) * MinHeap {
var me *MinHeap = &MinHeap {}
me.capacity = capacity
me.node = make([]*HeapNode, capacity + 1)
me.indexes = make([] int, capacity)
me.node[0] = getHeapNode()
me.node[0].key = math.MinInt64
me.node[0].vertex = -1
me.currentSize = 0
return me
}
func(this MinHeap) swap(a, b int) {
var temp * HeapNode = this.node[a]
this.node[a] = this.node[b]
this.node[b] = temp
}
func(this MinHeap) isEmpty() bool {
return this.currentSize == 0
}
func(this MinHeap) heapSize() int {
return this.currentSize
}
func(this MinHeap) bubbleUp(pos int) {
var parentIdx int = pos / 2
var currentIdx int = pos
for (currentIdx > 0 &&
this.node[parentIdx].key > this.node[currentIdx].key) {
var currentNode * HeapNode = this.node[currentIdx]
var parentNode * HeapNode = this.node[parentIdx]
this.indexes[currentNode.vertex] = parentIdx
this.indexes[parentNode.vertex] = currentIdx
this.swap(currentIdx, parentIdx)
currentIdx = parentIdx
parentIdx = parentIdx / 2
}
}
func(this *MinHeap) insert(x * HeapNode) {
this.currentSize++
var idx int = this.currentSize
this.node[idx] = x
this.indexes[x.vertex] = idx
this.bubbleUp(idx)
}
func(this *MinHeap) extractMin() * HeapNode {
var min * HeapNode = this.node[1]
var lastNode * HeapNode = this.node[this.currentSize]
this.indexes[lastNode.vertex] = 1
this.node[1] = lastNode
this.node[this.currentSize] = nil
this.sinkDown(1)
this.currentSize--
return min
}
func(this MinHeap) sinkDown(k int) {
var smallest int = k
// left child
var leftChild int = 2 * k
// right child
var rightChild int = 2 * k + 1
if leftChild < this.heapSize() &&
this.node[smallest].key > this.node[leftChild].key {
smallest = leftChild
}
if rightChild < this.heapSize() &&
this.node[smallest].key > this.node[rightChild].key {
smallest = rightChild
}
if smallest != k {
var smallestNode * HeapNode = this.node[smallest]
var kNode * HeapNode = this.node[k]
this.indexes[smallestNode.vertex] = k
this.indexes[kNode.vertex] = smallest
this.swap(k, smallest)
this.sinkDown(smallest)
}
}
type Graph struct {
vertices int
}
func getGraph(vertices int) * Graph {
var me *Graph = &Graph {}
me.vertices = vertices
for i := 0 ; i < me.vertices ; i++ {
}
return me
}
func(this *Graph) addEdge(u, v, weight int) {
if u == v {
// self loop
return
}
}
func(this Graph) decreaseKey(minHeap * MinHeap, newKey int, vertex int) {
var index int = minHeap.indexes[vertex]
var node * HeapNode = minHeap.node[index]
node.key = newKey
minHeap.bubbleUp(index)
}
func(this Graph) primMST() {
var inHeap = make([] bool, this.vertices)
var resultSet = make([] *ResultSet, this.vertices)
var key = make([] int, this.vertices)
var heapNodes = make([] *HeapNode, this.vertices)
// Set default value of heap nodes resultset and keys
for i := 0 ; i < this.vertices ; i++ {
heapNodes[i] = getHeapNode()
heapNodes[i].vertex = i
heapNodes[i].key = math.MaxInt64
resultSet[i] = getResultSet()
resultSet[i].parent = -1
inHeap[i] = true
key[i] = math.MaxInt64
}
heapNodes[0].key = 0
var minHeap * MinHeap = getMinHeap(this.vertices)
for j := 0 ; j < this.vertices ; j++ {
minHeap.insert(heapNodes[j])
}
var i int = 0
for (minHeap.isEmpty() == false) {
var extractedNode * HeapNode = minHeap.extractMin()
var extractedVertex int = extractedNode.vertex
inHeap[extractedVertex] = false
var edge * Edge = this.adjacencylist[extractedVertex][i]
if inHeap[edge.v] {
var v int = edge.v
var w int = edge.weight
if key[v] > w {
key[v] = w
this.decreaseKey(minHeap, w, v)
resultSet[v].parent = extractedVertex
resultSet[v].weight = w
}
}
i++
}
i = 0
}
var result int = 0
fmt.Print("\n\n Minimum Spanning Tree \n")
for node := 1 ; node < this.vertices ; node++ {
fmt.Println(" Edge (",
resultSet[node].parent, "-",
node, ")  weight : ", resultSet[node].weight)
result += resultSet[node].weight
}
// Display calculated result
fmt.Println(" Total minimum weight : ", result)
}
// Display graph nodes and edges
func(this Graph) printGraph() {
for i := 0 ; i < this.vertices ; i++ {
fmt.Print(" \n [", i, "] :")
// iterate edges of i node
for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
}
}
}
func main() {
var g * Graph = getGraph(10)
// Display graph element
g.printGraph()
g.primMST()
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8

Minimum Spanning Tree
Edge ( 8 - 1 )  weight :  6
Edge ( 3 - 2 )  weight :  8
Edge ( 9 - 3 )  weight :  5
Edge ( 5 - 4 )  weight :  15
Edge ( 9 - 5 )  weight :  7
Edge ( 7 - 6 )  weight :  2
Edge ( 0 - 7 )  weight :  6
Edge ( 0 - 8 )  weight :  4
Edge ( 8 - 9 )  weight :  3
Total minimum weight :  56
``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post