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
Prim's algorithm using adjacency list
*/
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)
{
this.adjacencylist.add(new ArrayList < Edge > ());
}
}
public void addEdge(int u, int v, int weight)
{
adjacencylist.get(u).add(new Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
adjacencylist.get(v).add(new Edge(v, u, weight));
}
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;
while (i < adjacencylist.get(extractedVertex).size())
{
Edge edge = adjacencylist.get(extractedVertex).get(i);
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()
{
System.out.print("\n Graph Adjacency List ");
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)
{
System.out.print(" " + this.adjacencylist.get(i).get(j).v);
}
}
}
public static void main(String[] args)
{
Graph g = new Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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
Prim's algorithm using adjacency list
*/
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)
{
this->adjacencylist.at(u).push_back(new Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
this->adjacencylist.at(v).push_back(new Edge(v, u, weight));
}
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;
while (i < this->adjacencylist.at(extractedVertex).size())
{
Edge *edge = this->adjacencylist.at(extractedVertex).at(i);
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);
g->addEdge(0, 1, 7);
g->addEdge(0, 7, 6);
g->addEdge(0, 8, 4);
g->addEdge(1, 2, 9);
g->addEdge(1, 8, 6);
g->addEdge(2, 3, 8);
g->addEdge(2, 6, 12);
g->addEdge(2, 9, 14);
g->addEdge(3, 4, 16);
g->addEdge(3, 9, 5);
g->addEdge(4, 5, 15);
g->addEdge(5, 6, 8);
g->addEdge(5, 9, 7);
g->addEdge(6, 7, 2);
g->addEdge(6, 8, 10);
g->addEdge(8, 9, 3);
// 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
Prim's algorithm using adjacency list
*/
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)
{
this.adjacencylist.Add(new List < Edge > ());
}
}
public void addEdge(int u, int v, int weight)
{
this.adjacencylist[u].Add(new Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
this.adjacencylist[v].Add(new Edge(v, u, weight));
}
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;
while (k < this.adjacencylist[extractedVertex].Count)
{
Edge edge = this.adjacencylist[extractedVertex][k];
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()
{
Console.Write("\n Graph Adjacency List ");
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)
{
Console.Write(" " + this.adjacencylist[i][j].v);
}
}
}
public static void Main(String[] args)
{
Graph g = new Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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
Prim's algorithm using adjacency list
*/
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 $adjacencylist;
public function __construct($vertices)
{
$this->vertices = $vertices;
$this->adjacencylist = array();
for ($i = 0; $i < $this->vertices; ++$i)
{
$this->adjacencylist[] = array();
}
}
public function addEdge($u, $v, $weight)
{
$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;
while ($i < count($this->adjacencylist[$extractedVertex]))
{
$edge = $this->adjacencylist[$extractedVertex][$i];
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()
{
echo("\n Graph Adjacency List ");
for ($i = 0; $i < $this->vertices; ++$i)
{
echo(" \n [".$i."] :");
// iterate edges of i node
for ($j = 0; $j < count($this->adjacencylist[$i]); ++$j)
{
echo(" ".$this->adjacencylist[$i][$j]->v);
}
}
}
}
function main()
{
$g = new Graph(10);
$g->addEdge(0, 1, 7);
$g->addEdge(0, 7, 6);
$g->addEdge(0, 8, 4);
$g->addEdge(1, 2, 9);
$g->addEdge(1, 8, 6);
$g->addEdge(2, 3, 8);
$g->addEdge(2, 6, 12);
$g->addEdge(2, 9, 14);
$g->addEdge(3, 4, 16);
$g->addEdge(3, 9, 5);
$g->addEdge(4, 5, 15);
$g->addEdge(5, 6, 8);
$g->addEdge(5, 9, 7);
$g->addEdge(6, 7, 2);
$g->addEdge(6, 8, 10);
$g->addEdge(8, 9, 3);
// 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
Prim's algorithm using adjacency list
*/
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;
this.adjacencylist = [];
for (var i = 0; i < this.vertices; ++i)
{
this.adjacencylist.push([]);
}
}
addEdge(u, v, weight)
{
this.adjacencylist[u].push(new Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
this.adjacencylist[v].push(new Edge(v, u, weight));
}
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;
while (i < this.adjacencylist[extractedVertex].length)
{
var edge = this.adjacencylist[extractedVertex][i];
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()
{
process.stdout.write("\n Graph Adjacency List ");
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)
{
process.stdout.write(" " + this.adjacencylist[i][j].v);
}
}
}
}
function main()
{
var g = new Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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 : 56import 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
self.adjacencylist = []
i = 0
while (i < self.vertices) :
self.adjacencylist.append([])
i += 1
def addEdge(self, u, v, weight) :
self.adjacencylist[u].append(Edge(u, v, weight))
if (u == v) :
# self loop
return
self.adjacencylist[v].append(Edge(v, u, weight))
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
while (i < len(self.adjacencylist[extractedVertex])) :
edge = self.adjacencylist[extractedVertex][i]
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
while (j < len(self.adjacencylist[i])) :
print(" ", self.adjacencylist[i][j].v, end = "")
j += 1
i += 1
def main() :
g = Graph(10)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
# 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_reader :u, :v, :weight
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_reader :vertex, :key
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_reader :parent, :weight
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_reader :capacity, :currentSize, :node, :indexes
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
attr_reader :vertices, :adjacencylist
attr_accessor :vertices, :adjacencylist
def initialize(vertices)
self.vertices = vertices
self.adjacencylist = []
i = 0
while (i < self.vertices)
self.adjacencylist.push([])
i += 1
end
end
def addEdge(u, v, weight)
self.adjacencylist[u].push(Edge.new(u, v, weight))
if (u == v)
# self loop
return
end
self.adjacencylist[v].push(Edge.new(v, u, weight))
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
while (i < self.adjacencylist[extractedVertex].length)
edge = self.adjacencylist[extractedVertex][i]
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()
print("\n Graph Adjacency List ")
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
# iterate edges of i node
while (j < self.adjacencylist[i].length)
print(" ", self.adjacencylist[i][j].v)
j += 1
end
i += 1
end
end
end
def main()
g = Graph.new(10)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
# 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
Prim's algorithm using adjacency list
*/
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,
var adjacencylist: ArrayBuffer[ArrayBuffer[Edge]])
{
def this(vertices: Int)
{
this(vertices,new ArrayBuffer[ArrayBuffer[Edge]](vertices));
var i: Int = 0;
while (i < this.vertices)
{
this.adjacencylist += new ArrayBuffer[Edge]();
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;
while (i < adjacencylist(extractedVertex).size)
{
var edge: Edge = adjacencylist(extractedVertex)(i);
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 = {
print("\n Graph Adjacency List ");
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.adjacencylist(i).size)
{
print(" " + this.adjacencylist(i)(j).v);
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var g: Graph = new Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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 : 56import Foundation;
/*
Swift 4 program for
Prim's algorithm using adjacency list
*/
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;
var adjacencylist: [
[Edge?]
];
init(_ vertices: Int)
{
self.vertices = vertices;
self.adjacencylist = [[Edge?]]();
var i: Int = 0;
while (i < self.vertices)
{
self.adjacencylist.append([Edge?]());
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int, _ weight: Int)
{
self.adjacencylist[u].append(Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
self.adjacencylist[v].append(Edge(v, u, weight));
}
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;
while (i < self.adjacencylist[extractedVertex].count)
{
let edge: Edge? = self.adjacencylist[extractedVertex][i];
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
while (j < self.adjacencylist[i].count)
{
print(" ", self.adjacencylist[i][j]!.v, terminator: "");
j += 1;
}
i += 1;
}
}
}
func main()
{
let g: Graph = Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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
Prim's algorithm using adjacency list
*/
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;
this.adjacencylist = mutableListOf<MutableList<Edge>>();
var i: Int = 0;
while (i < this.vertices)
{
this.adjacencylist.add(mutableListOf<Edge>());
i += 1;
}
}
fun addEdge(u: Int, v: Int, weight: Int): Unit
{
this.adjacencylist[u].add(Edge(u, v, weight));
if (u == v)
{
// self loop
return;
}
this.adjacencylist[v].add(Edge(v, u, weight));
}
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;
while (i < this.adjacencylist[extractedVertex].size)
{
val edge: Edge? = this.adjacencylist[extractedVertex][i];
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
{
print("\n Graph Adjacency List ");
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.adjacencylist[i].size)
{
print(" " + this.adjacencylist[i][j].v);
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val g: Graph = Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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 : 56package main
import "math"
import "fmt"
/*
Go program for
Prim's algorithm using adjacency list
*/
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
adjacencylist [][]*Edge
}
func getGraph(vertices int) * Graph {
var me *Graph = &Graph {}
me.vertices = vertices
me.adjacencylist = make([][]*Edge,vertices)
for i := 0 ; i < me.vertices ; i++ {
me.adjacencylist = append(me.adjacencylist)
}
return me
}
func(this *Graph) addEdge(u, v, weight int) {
this.adjacencylist[u] = append(this.adjacencylist[u], getEdge(u, v, weight))
if u == v {
// self loop
return
}
this.adjacencylist[v] = append(this.adjacencylist[v], getEdge(v, u, weight))
}
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
for (i < len(this.adjacencylist[extractedVertex])) {
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() {
fmt.Print("\n Graph Adjacency List ")
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++ {
fmt.Print(" ", this.adjacencylist[i][j].v)
}
}
}
func main() {
var g * Graph = getGraph(10)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
// 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
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.
New Comment