Skip to main content

Prim's algorithm using adjacency matrix

Here given code implementation process.

Minimum spanning tree example 
// Include header file
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

/*
    C program for
    Prim's algorithm using adjacency matrix
*/
#define Vertices 10

int minCost(int cost[], bool recognize[])
{
    int min = INT_MAX;
    int position = -1;
    for (int v = 0; v < Vertices; ++v)
    {
        if (recognize[v] == false && cost[v] < min)
        {
            min = cost[v];
            position = v;
        }
    }
    return position;
}

void primMST(int matrix[Vertices][Vertices])
{
    // Define some auxiliary storage
    bool recognize[Vertices];
    int parent[Vertices];
    int cost[Vertices];
    // Set default value
    for (int i = 0; i < Vertices; i++)
    {
        cost[i] = INT_MAX;
        recognize[i] = false;
    }
    // Set defualt value
    cost[0] = 0;
    parent[0] = -1;
    for (int node = 0; node < Vertices - 1; ++node)
    {
        int u = minCost(cost, recognize);
        recognize[u] = true;
        for (int v = 0; v < Vertices; v++)
        {
            if (matrix[u][v] != 0 
                && recognize[v] == false && matrix[u][v] < cost[v])
            {
                parent[v] = u;
                cost[v] = matrix[u][v];
            }
        }
    }
    int result = 0;
    // Display resultant edges
    printf("  Edge    Weight\n");
    for (int i = 1; i < Vertices; i++)
    {
        // Display edges and weight
        printf(" (%d - %d)    %d\n",parent[i], i,matrix[i][parent[i]] );
     
        // Sum of the edge weight
        result += matrix[i][parent[i]];
    }
    // Display minimum weight
   printf(" Total minimum weight : %d\n", result );
}
int main()
{
    // Define edge weight
    int matrix[Vertices][Vertices] = {
        {
            0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
        } , {
            7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
        } , {
            0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
        } , {
            0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
        } , {
            0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
        } , {
            0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
        } , {
            0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
        } , {
            6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
        } , {
            4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
        } , {
            0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
        }
    };
    // Print the solution 
    primMST(matrix);
    return 0;
}

input

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

using namespace std;
/*
    C++ program for
    Prim's algorithm using adjacency matrix
*/
#define Vertices 10
class Graph
{
	public:
	int minCost(int cost[], bool recognize[])
	{
		int min = INT_MAX;
		int position = -1;
		for (int v = 0; v < Vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	void primMST(int matrix[Vertices][Vertices])
	{
		// Define some auxiliary storage
		bool recognize[Vertices];
		int parent[Vertices];
		int cost[Vertices];
		// Set default value
		for (int i = 0; i < Vertices; i++)
		{
			cost[i] = INT_MAX;
			recognize[i] = false;
		}
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (int node = 0; node < Vertices - 1; ++node)
		{
			int u = this->minCost(cost, recognize);
			recognize[u] = true;
			for (int v = 0; v < Vertices; v++)
			{
				if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
			}
		}
		int result = 0;
		// Display resultant edges
		cout << "  Edge    Weight" << endl;
		for (int i = 1; i < Vertices; i++)
		{
			// Display edges and weight
			cout << " (" << parent[i] << " - " << i 
          		 << ")    " << matrix[i][parent[i]] << endl;
			// Sum of the edge weight
			result += matrix[i][parent[i]];
		}
		// Display minimum weight
		cout << " Total minimum weight : " << result << endl;
	}
};
int main()
{
	// Define edge weight
	int matrix[Vertices][Vertices] = {
		{
			0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
		} , {
			7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
		} , {
			0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
		} , {
			0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
		} , {
			0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
		} , {
			0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
		} , {
			0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
		} , {
			6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
		} , {
			4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
		} , {
			0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
		}
	};
	// Get number of vertices	

	Graph *g = new Graph();
	// Print the solution 
	g->primMST(matrix);
	return 0;
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
/*
    Java program for
    Prim's algorithm using adjacency matrix
*/

public class Graph
{
    public int vertices;

    public Graph(int vertices)
    {
        this.vertices = vertices;
    }

    int minCost(int []cost, boolean []recognize)
    {
       
        int min = Integer.MAX_VALUE;

        int position = -1;

        for (int v = 0; v < this.vertices; ++v)
        {
            if (recognize[v] == false && cost[v] < min)
            {
                min = cost[v];
                position = v;
            } 
        }
         
        return position;
    }
   

    void primMST(int [][]matrix)
    {
        
        // Define some auxiliary storage
        boolean []recognize = new boolean[this.vertices];
        int []parent = new int[this.vertices];
        int []cost = new int[this.vertices];


        // Set default value
        for (int i = 0; i < this.vertices; i++)
        {
            cost[i] = Integer.MAX_VALUE;
            recognize[i] = false;
        }
        // Set defualt value
        cost[0] = 0;  

        parent[0] = -1; 

        for (int node = 0; node < this.vertices - 1; ++node)
        {
            
            int u = minCost(cost, recognize);
       
            recognize[u] = true;
         
            for (int v = 0; v < this.vertices; v++)
            {

                if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
                {
                    parent[v] = u;
                    cost[v] = matrix[u][v];
                }
            }

        }
      
        int result = 0;

        // Display resultant edges
        System.out.println("  Edge    Weight");
        for (int i = 1; i < this.vertices; i++)
        {
            // Display edges and weight
             System.out.print(" ("+parent[i] + " - " + i + ")    " + 
                              matrix[i][parent[i]]+"\n");
             // Sum of the edge weight
             result += matrix[i][parent[i]];
        }
        // Display minimum weight
        System.out.println(" Total minimum weight : " + result);
    }
    public static void main(String[] args)
    {
      	// Define edge weight
        int [][]matrix =
        {
            {
                0, 7, 0, 0, 0, 0, 0, 6, 4, 0
            },
            {
                7, 0, 9, 0, 0, 0, 0, 0, 6, 0
            },
            {
                0, 9, 0, 8, 0, 0, 12, 0, 0, 14
            },
            {
                0, 0, 8, 16, 0, 0, 0, 0, 0, 5
            },
            {
                0, 0 , 0, 16, 0, 15, 0, 0, 0, 0
            },
            {
                0, 0, 0, 0, 15, 0, 8, 0, 0, 7
            },
            {
                0, 0, 12, 0, 0, 8, 0, 2, 10, 0
            },
            {
                6, 0, 0, 0, 0, 0, 2, 0, 0, 0
            },
            {
                4, 6, 0, 0, 0, 0, 10, 0, 0, 3
            },
            {
                0, 0, 14, 5, 0, 7, 0, 0, 3, 0
            }
        };
		// Get number of vertices	
        int n = matrix[0].length;
		
        Graph g = new Graph(n);
      
        // Print the solution 
        g.primMST(matrix);
    }
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
package main
import "math"
import "fmt"
/*
    Go program for
    Prim's algorithm using adjacency matrix
*/

func minCost(cost[] int, recognize[] bool, vertices int) int {
	var min int = math.MaxInt64
	var position int = -1
	for v := 0 ; v < vertices ; v++ {
		if recognize[v] == false && cost[v] < min {
			min = cost[v]
			position = v
		}
	}
	return position
}
func primMST(matrix[][] int,vertices int) {
	// Define some auxiliary storage
	var recognize =  make([] bool,vertices)
	var parent = make([] int,vertices)
	var cost = make([] int,vertices)
	// Set default value
	for i := 0 ; i < vertices ; i++ {
		cost[i] = math.MaxInt64
		recognize[i] = false
	}
	// Set defualt value
	cost[0] = 0
	parent[0] = -1
	for node := 0 ; node < vertices - 1 ; node++ {
		var u int = minCost(cost, recognize, vertices)
		recognize[u] = true
		for v := 0 ; v < vertices ; v++ {
			if matrix[u][v] != 0 && 
				recognize[v] == false && matrix[u][v] < cost[v] {
				parent[v] = u
				cost[v] = matrix[u][v]
			}
		}
	}
	var result int = 0
	// Display resultant edges
	fmt.Println("  Edge    Weight")
	for i := 1 ; i < vertices ; i++ {
		// Display edges and weight
		fmt.Print(" (", parent[i], " - ", i, ")    ", 
						matrix[i][parent[i]], "\n")
		// Sum of the edge weight
		result += matrix[i][parent[i]]
	}
	// Display minimum weight
	fmt.Println(" Total minimum weight : ", result)
}
func main() {
	// Define edge weight
	var matrix = [][] int {
		{
			0,
			7,
			0,
			0,
			0,
			0,
			0,
			6,
			4,
			0,
		}, {
			7,
			0,
			9,
			0,
			0,
			0,
			0,
			0,
			6,
			0,
		}, {
			0,
			9,
			0,
			8,
			0,
			0,
			12,
			0,
			0,
			14,
		}, {
			0,
			0,
			8,
			16,
			0,
			0,
			0,
			0,
			0,
			5,
		}, {
			0,
			0,
			0,
			16,
			0,
			15,
			0,
			0,
			0,
			0,
		}, {
			0,
			0,
			0,
			0,
			15,
			0,
			8,
			0,
			0,
			7,
		}, {
			0,
			0,
			12,
			0,
			0,
			8,
			0,
			2,
			10,
			0,
		}, {
			6,
			0,
			0,
			0,
			0,
			0,
			2,
			0,
			0,
			0,
		}, {
			4,
			6,
			0,
			0,
			0,
			0,
			10,
			0,
			0,
			3,
		}, {
			0,
			0,
			14,
			5,
			0,
			7,
			0,
			0,
			3,
			0,
		},
	}
	// Get number of vertices	
	var n int = len(matrix[0])
	
	// Print the solution 
	primMST(matrix, n)
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
// Include namespace system
using System;
/*
    Csharp program for
    Prim's algorithm using adjacency matrix
*/
public class Graph
{
	public int vertices;
	public Graph(int vertices)
	{
		this.vertices = vertices;
	}
	int minCost(int[] cost, Boolean[] recognize)
	{
		int min = int.MaxValue;
		int position = -1;
		for (int v = 0; v < this.vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	void primMST(int[,] matrix)
	{
		// Define some auxiliary storage
		Boolean[] recognize = new Boolean[this.vertices];
		int[] parent = new int[this.vertices];
		int[] cost = new int[this.vertices];
		// Set default value
		for (int i = 0; i < this.vertices; i++)
		{
			cost[i] = int.MaxValue;
			recognize[i] = false;
		}
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (int node = 0; node < this.vertices - 1; ++node)
		{
			int u = this.minCost(cost, recognize);
			recognize[u] = true;
			for (int v = 0; v < this.vertices; v++)
			{
				if (matrix[u,v] != 0 
                    && recognize[v] == false && matrix[u,v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u,v];
				}
			}
		}
		int result = 0;
		// Display resultant edges
		Console.WriteLine("  Edge    Weight");
		for (int i = 1; i < this.vertices; i++)
		{
			// Display edges and weight
			Console.Write(" (" + parent[i] + " - " + i + ")    " 
                          + matrix[i,parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i,parent[i]];
		}
		// Display minimum weight
		Console.WriteLine(" Total minimum weight : " + result);
	}
	public static void Main(String[] args)
	{
		// Define edge weight
		int[,] matrix = {
			{
				0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
			},
			{
				7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
			},
			{
				0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
			},
			{
				0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
			},
			{
				0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
			},
			{
				0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
			},
			{
				0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
			},
			{
				6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
			},
			{
				4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
			},
			{
				0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
			}
		};
		// Get number of vertices	
		int n = matrix.GetLength(0);
		Graph g = new Graph(n);
		// Print the solution 
		g.primMST(matrix);
	}
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
<?php
/*
    Php program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	public $vertices;
	public	function __construct($vertices)
	{
		$this->vertices = $vertices;
	}

	function minCost($cost, $recognize)
	{
		$min = PHP_INT_MAX;
		$position = -1;
		for ($v = 0; $v < $this->vertices; ++$v)
		{
			if ($recognize[$v] == false && $cost[$v] < $min)
			{
				$min = $cost[$v];
				$position = $v;
			}
		}
		return $position;
	}

	function primMST($matrix)
	{
		// Define some auxiliary storage
		$recognize = array_fill(0, $this->vertices, false);
		$parent = array_fill(0, $this->vertices, 0);
		$cost = array_fill(0, $this->vertices, PHP_INT_MAX);
		// Set defualt value
		$cost[0] = 0;
		$parent[0] = -1;
		for ($node = 0; $node < $this->vertices - 1; ++$node)
		{
			$u = $this->minCost($cost, $recognize);
			$recognize[$u] = true;
			for ($v = 0; $v < $this->vertices; $v++)
			{
				if ($matrix[$u][$v] != 0 
                    && $recognize[$v] == false && $matrix[$u][$v] < $cost[$v])
				{
					$parent[$v] = $u;
					$cost[$v] = $matrix[$u][$v];
				}
			}
		}
		$result = 0;
		// Display resultant edges
		echo("  Edge    Weight\n");
		for ($i = 1; $i < $this->vertices; $i++)
		{
			// Display edges and weight
			echo(" (".$parent[$i]." - ".$i.
				")    ".$matrix[$i][$parent[$i]]."\n");
			// Sum of the edge weight
			$result += $matrix[$i][$parent[$i]];
		}
		// Display minimum weight
		echo(" Total minimum weight : ".$result."\n");
	}
}

function main()
{
	// Define edge weight
	$matrix = array(
      array(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
      array(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
      array(0, 9, 0, 8, 0, 0, 12, 0, 0, 14), 
      array(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
      array(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
      array(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
      array(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
      array(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
      array(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
      array(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
    );
	// Get number of vertices	
	$n = count($matrix[0]);
	$g = new Graph($n);
	// Print the solution 
	$g->primMST($matrix);
}
main();

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
/*
    Node JS program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	constructor(vertices)
	{
		this.vertices = vertices;
	}
	minCost(cost, recognize)
	{
		var min = Number.MAX_VALUE;
		var position = -1;
		for (var v = 0; v < this.vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	primMST(matrix)
	{
		// Define some auxiliary storage
		var recognize = Array(this.vertices).fill(false);
		var parent = Array(this.vertices).fill(0);
		var cost = Array(this.vertices).fill(Number.MAX_VALUE);
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (var node = 0; node < this.vertices - 1; ++node)
		{
			var u = this.minCost(cost, recognize);
			recognize[u] = true;
			for (var v = 0; v < this.vertices; v++)
			{
				if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
			}
		}
		var result = 0;
		// Display resultant edges
		console.log("  Edge    Weight");
		for (var i = 1; i < this.vertices; i++)
		{
			// Display edges and weight
			process.stdout.write(" (" + parent[i] + " - " + i + 
                                 ")    " + matrix[i][parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i][parent[i]];
		}
		// Display minimum weight
		console.log(" Total minimum weight : " + result);
	}
}

function main()
{
	// Define edge weight
	var matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	];
	// Get number of vertices	
	var n = matrix[0].length;
	var g = new Graph(n);
	// Print the solution 
	g.primMST(matrix);
}
main();

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
import sys
#    Python 3 program for
#    Prim's algorithm using adjacency matrix
class Graph :
	def __init__(self, vertices) :
		self.vertices = vertices
	
	def minCost(self, cost, recognize) :
		min = sys.maxsize
		position = -1
		v = 0
		while (v < self.vertices) :
			if (recognize[v] == False and cost[v] < min) :
				min = cost[v]
				position = v
			
			v += 1
		
		return position
	
	def primMST(self, matrix) :
		#  Define some auxiliary storage
		recognize = [False] * (self.vertices)
		parent = [0] * (self.vertices)
		cost = [0] * (self.vertices)
		i = 0
		#  Set default value
		while (i < self.vertices) :
			cost[i] = sys.maxsize
			recognize[i] = False
			i += 1
		
		#  Set defualt value
		cost[0] = 0
		parent[0] = -1
		node = 0
		while (node < self.vertices - 1) :
			u = self.minCost(cost, recognize)
			recognize[u] = True
			v = 0
			while (v < self.vertices) :
				if (matrix[u][v] != 0 and 
                    recognize[v] == False and matrix[u][v] < cost[v]) :
					parent[v] = u
					cost[v] = matrix[u][v]
				
				v += 1
			
			node += 1
		
		result = 0
		#  Display resultant edges
		print("  Edge    Weight")
		i = 1
		while (i < self.vertices) :
			#  Display edges and weight
			print("(", parent[i] ,"-", i ,")   ", matrix[i][parent[i]] )
			#  Sum of the edge weight
			result += matrix[i][parent[i]]
			i += 1
		
		#  Display minimum weight
		print(" Total minimum weight : ", result)
	

def main() :
	#  Define edge weight
	matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	]
	#  Get number of vertices	
	n = len(matrix[0])
	g = Graph(n)
	#  Print the solution 
	g.primMST(matrix)

if __name__ == "__main__": main()

input

  Edge    Weight
( 8 - 1 )    6
( 3 - 2 )    8
( 9 - 3 )    5
( 5 - 4 )    15
( 9 - 5 )    7
( 7 - 6 )    2
( 0 - 7 )    6
( 0 - 8 )    4
( 8 - 9 )    3
 Total minimum weight :  56
#    Ruby program for
#    Prim's algorithm using adjacency matrix
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices
	attr_accessor :vertices
	def initialize(vertices) 
		self.vertices = vertices
	end

	def minCost(cost, recognize) 
		min = (2 ** (0. size * 8 - 2))
		position = -1
		v = 0
		while (v < self.vertices) 
			if (recognize[v] == false && cost[v] < min) 
				min = cost[v]
				position = v
			end

			v += 1
		end

		return position
	end

	def primMST(matrix) 
		#  Define some auxiliary storage
		recognize = Array.new(self.vertices) {false}
		parent = Array.new(self.vertices) {0}
		cost = Array.new(self.vertices) {0}
		i = 0
		#  Set default value
		while (i < self.vertices) 
			cost[i] = (2 ** (0. size * 8 - 2))
			recognize[i] = false
			i += 1
		end

		#  Set defualt value
		cost[0] = 0
		parent[0] = -1
		node = 0
		while (node < self.vertices - 1) 
			u = self.minCost(cost, recognize)
			recognize[u] = true
			v = 0
			while (v < self.vertices) 
				if (matrix[u][v] != 0 && 
                    recognize[v] == false && matrix[u][v] < cost[v]) 
					parent[v] = u
					cost[v] = matrix[u][v]
				end

				v += 1
			end

			node += 1
		end

		result = 0
		#  Display resultant edges
		print("  Edge    Weight", "\n")
		i = 1
		while (i < self.vertices) 
			#  Display edges and weight
			print(" (", parent[i] ," - ", i ,")    ", 
                  matrix[i][parent[i]] ,"\n")
			#  Sum of the edge weight
			result += matrix[i][parent[i]]
			i += 1
		end

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

end

def main() 
	#  Define edge weight
	matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	]
	#  Get number of vertices	
	n = matrix[0].length
	g = Graph.new(n)
	#  Print the solution 
	g.primMST(matrix)
end

main()

input

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

/*
    Scala program for
    Prim's algorithm using adjacency matrix
*/
class Graph(var vertices: Int)
{
	def minCost(cost: Array[Int], 
      recognize: Array[Boolean]): Int = {
		var min: Int = Int.MaxValue;
		var position: Int = -1;
		var v: Int = 0;
		while (v < this.vertices)
		{
			if (recognize(v) == false && cost(v) < min)
			{
				min = cost(v);
				position = v;
			}
			v += 1;
		}
		return position;
	}
	def primMST(matrix: Array[Array[Int]]): Unit = {
		// Define some auxiliary storage
		var recognize: Array[Boolean] = 
          Array.fill[Boolean](this.vertices)(false);
		var parent: Array[Int] =
          Array.fill[Int](this.vertices)(0);
		var cost: Array[Int] = 
          Array.fill[Int](this.vertices)(Int.MaxValue);
		// Set defualt value
		cost(0) = 0;
		parent(0) = -1;
		var node: Int = 0;
		while (node < this.vertices - 1)
		{
			var u: Int = minCost(cost, recognize);
			recognize(u) = true;
			var v: Int = 0;
			while (v < this.vertices)
			{
				if (matrix(u)(v) != 0 
                    && recognize(v) == false && matrix(u)(v) < cost(v))
				{
					parent(v) = u;
					cost(v) = matrix(u)(v);
				}
				v += 1;
			}
			node += 1;
		}
		var result: Int = 0;
		// Display resultant edges
		println("  Edge    Weight");
		var i: Int = 1;
		while (i < this.vertices)
		{
			// Display edges and weight
			print(" (" + parent(i) + " - " + i + ")    " + 
                  matrix(i)(parent(i)) + "\n");
			// Sum of the edge weight
			result += matrix(i)(parent(i));
			i += 1;
		}
		// Display minimum weight
		println(" Total minimum weight : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Define edge weight
		var matrix: Array[Array[Int]] = Array(
          Array(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
          Array(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
          Array(0, 9, 0, 8, 0, 0, 12, 0, 0, 14),
          Array(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
          Array(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
          Array(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
          Array(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
          Array(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
          Array(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
          Array(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
        );
		// Get number of vertices	
		var n: Int = matrix(0).length;
		var g: Graph = new Graph(n);
		// Print the solution 
		g.primMST(matrix);
	}
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
import Foundation;
/*
    Swift 4 program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	var vertices: Int;
	init(_ vertices: Int)
	{
		self.vertices = vertices;
	}
	func minCost(_ cost: [Int], _ recognize: [Bool]) -> Int
	{
		var min = Int.max;
		var position = -1;
		var v = 0;
		while (v < self.vertices)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
			v += 1;
		}
		return position;
	}
	func primMST(_ matrix: [
		[Int]
	])
	{
		// Define some auxiliary storage
		var recognize = Array(repeating: false, count: self.vertices);
		var parent = Array(repeating: 0, count: self.vertices);
		var cost = Array(repeating: Int.max, count: self.vertices);
	
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		var node = 0;
		while (node < self.vertices - 1)
		{
			let u = self.minCost(cost, recognize);
			recognize[u] = true;
			var v = 0;
			while (v < self.vertices)
			{
				if (matrix[u][v]  != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
				v += 1;
			}
			node += 1;
		}
		var result = 0;
		// Display resultant edges
		print("  Edge    Weight");
		var i = 1;
		while (i < self.vertices)
		{
			// Display edges and weight
			print("(", parent[i] ,"-", i ,")  ", matrix[i][parent[i]] );
			// Sum of the edge weight
			result += matrix[i][parent[i]];
			i += 1;
		}
		// Display minimum weight
		print(" Total minimum weight : ", result);
	}
}
func main()
{
	// Define edge weight
	let matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	];
	// Get number of vertices	
	let n = matrix[0].count;
	let g = Graph(n);
	// Print the solution 
	g.primMST(matrix);
}
main();

input

  Edge    Weight
( 8 - 1 )   6
( 3 - 2 )   8
( 9 - 3 )   5
( 5 - 4 )   15
( 9 - 5 )   7
( 7 - 6 )   2
( 0 - 7 )   6
( 0 - 8 )   4
( 8 - 9 )   3
 Total minimum weight :  56
/*
    Kotlin program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	var vertices: Int;
	constructor(vertices: Int)
	{
		this.vertices = vertices;
	}
	fun minCost(cost: Array < Int > , recognize: Array < Boolean > ): Int
	{
		var min: Int = Int.MAX_VALUE;
		var position: Int = -1;
		var v: Int = 0;
		while (v < this.vertices)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
			v += 1;
		}
		return position;
	}
	fun primMST(matrix: Array < Array < Int >> ): Unit
	{
		// Define some auxiliary storage
		var recognize: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		var parent: Array < Int > = Array(this.vertices)
		{
			0
		};
		var cost: Array < Int > = Array(this.vertices)
		{
			Int.MAX_VALUE
		};
	
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		var node: Int = 0;
		while (node < this.vertices - 1)
		{
			val u: Int = this.minCost(cost, recognize);
			recognize[u] = true;
			var v: Int = 0;
			while (v < this.vertices)
			{
				if (matrix[u][v] != 0 && 
                    recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
				v += 1;
			}
			node += 1;
		}
		var result: Int = 0;
		// Display resultant edges
		println("  Edge    Weight");
		var i: Int = 1;
		while (i < this.vertices)
		{
			// Display edges and weight
			print(" (" + parent[i] + " - " + i + ")    " + 
                  matrix[i][parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i][parent[i]];
			i += 1;
		}
		// Display minimum weight
		println(" Total minimum weight : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	// Define edge weight
	val matrix: Array < Array < Int >> = arrayOf(
      arrayOf(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
      arrayOf(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
      arrayOf(0, 9, 0, 8, 0, 0, 12, 0, 0, 14), 
      arrayOf(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
      arrayOf(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
      arrayOf(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
      arrayOf(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
      arrayOf(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
      arrayOf(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
      arrayOf(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
    );
	// Get number of vertices	
	val n: Int = matrix[0].count();
	val g: Graph = Graph(n);
	// Print the solution 
	g.primMST(matrix);
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
Last updated on by Kalkicode




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.

New Comment