The Minimum Spanning Tree - Prim's Algorithm
Written by Mike James
Thursday, 25 February 2016
Article Index
The Minimum Spanning Tree - Prim's Algorithm
Prim's Algorithm In C#
Implementing Prim's algorithm
Listing

## Listing

The complete listing is:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Shapes;

namespace Prim
{

public partial class MainWindow : Window
{
const int size = 10;
private Point[] Positions = new Point[size];
private Single[,] Network =
new Single[size, size];
private Random R = new Random();

public MainWindow()
{
InitializeComponent();
}

private void setnet(Single[,] Net, Point[] Pos)
{
int maxlength = (int)(Math.Min(canvas1.Width,
canvas1.Height) * 0.9);
int minlength = maxlength / size;
for (int i = 0; i < size; i++)
{
Pos[i].X = R.Next(minlength, maxlength);
Pos[i].Y = R.Next(minlength, maxlength);
for (int j = 0; j <= i; j++)
{
Net[i, j] = distance(Pos[i], Pos[j]);
Net[j, i] = Net[i, j];
if (i == j) Net[i, j] = 0;
}
}
}

private Single distance(Point a, Point b)
{
return (Single)Math.Sqrt((a.X - b.X) *
(a.X - b.X) +
(a.Y - b.Y) *
(a.Y - b.Y));
}

private void shownet(Single[,] Net)
{
canvas1.Children.Clear();
Line myLine;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < i; j++)
{
if (Net[i, j] != 0)
{
myLine = new Line();
myLine.Stroke = Brushes.Black;
myLine.X1 = Positions[i].X;
myLine.X2 = Positions[j].X;
myLine.Y1 = Positions[i].Y;
myLine.Y2 = Positions[j].Y;
myLine.StrokeThickness = 1;
}
}
}

Rectangle myMarker;
for (int i = 0; i < size; i++)
{
myMarker = new Rectangle();
myMarker.Stroke = Brushes.Black;
myMarker.Fill = Brushes.Red;
myMarker.Height = 10;
myMarker.Width = 10;
myMarker.SetValue(Canvas.TopProperty,
Positions[i].Y - myMarker.Height / 2);
myMarker.SetValue(Canvas.LeftProperty,
Positions[i].X - myMarker.Width / 2);
}
}

private void button_Click(object sender,
RoutedEventArgs e)
{
canvas1.Width = 600;
canvas1.Height = 600;
setnet(Network, Positions);
shownet(Network);
}

private void Find_MST_Click(object sender,
RoutedEventArgs e)
{
prims();
}

void prims()
{
int[] included = new int[size];
int[] excluded = new int[size];
Single[,] finished = new Single[size, size];
int start = 0;

int finish = 0;
for (int i = 0; i < size; i++)

{
excluded[i] = i;
included[i] = -1;
}
included[0] = excluded[R.Next(size)];
excluded[included[0]] = -1;
for (int n = 1; n < size; n++)
{
closest(n, ref start, ref finish,
included, excluded);
included[n] = excluded[finish];
excluded[finish] = -1;
finished[included[n], included[start]] =
Network[included[n], included[start]];
finished[included[start], included[n]] =
Network[included[start], included[n]];
}
shownet(finished);
}

private void closest(int n, ref int start,
ref int finish,int[] included, int[] excluded)
{
Single smallest = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < size; j++)
{
if (excluded[j] == -1) continue;
if (smallest == -1) smallest =
Network[included[i], excluded[j]];
if (Network[included[i], excluded[j]] >
smallest) continue;
smallest = Network[included[i], excluded[j]];
start = i;
finish = j;
}
}
}
}
}

 The Minimum Spanning Tree - Prim's Algorithm In PythonFinding the minimum spanning tree is one of the fundamental algorithms and it is important in computer science and practical programming. We take a look at the theory and the practice and discover how [ ... ] + Full Project Setting Up Site-To-Site OpenVPN Setting up a point-to-point VPN is relatively easy but site-to-site is much more complicated involving certificates and more IP addresses than you can count. Find out how to do it using OpenVPN. + Full Project Other Projects

 JetBrains RustRover Now Commercially Available24/05/2024JetBrains has announced the commercial release of RustRover, an IDE for Rust developers. The company describes RustRover  as combining advanced coding support with an integrated toolchain. + Full Story Celebrating Alan Turing 07/06/2024Today, June 7th 2024 is the 70th anniversary of the untimely death of Alan Turing. While we now commemorate him for his contributions to code-breaking computer science and artificial intelligence, sev [ ... ] + Full Story More News