The Minimum Spanning Tree In C# - Prim's or Dijkstra Algorithm
Written by Mike James   
Sunday, 06 October 2024
Article Index
The Minimum Spanning Tree In C# - Prim's or Dijkstra Algorithm
Prim's Algorithm In C#
Implementing Prim's algorithm
Listing

Listing

The complete listing is:

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.Navigation;
using System.Windows.Shapes;

namespace WpfApp1
{

    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;
                        canvas1.Children.Add(myLine);
                    }
                }
            }

            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);
                canvas1.Children.Add(myMarker);
            }
        }


        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;
                }
            }
        }

        private void Button_Click_1(object sender,
                                                    RoutedEventArgs e)
        {

            canvas1.Width = 600;
            canvas1.Height = 600;
            setnet(Network, Positions);
            shownet(Network);
        }

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

Mike James, Founder and Chief Editor of I Programmer is a prolific author. In Deep C#: Dive Into Modern C#, published in September 2021, he provides a “deep dive” into various topics that are important or central to the language. By exploring the motivation behind these key concepts, which is so often ignored in the documentation, the intention is to be thought-provoking and to give developers confidence to exploit C#’s wide range of features.

Related Articles

The Minimum Spanning Tree - Prim's Algorithm In Python


Disk Drive Dangers - SMART and WMI

Getting access from an application to the hardware is never easy. If you want to know how well your disk drive is performing then there is a way of accessing the SMART data - including the temper [ ... ]



AWS Low Cost Mailing List Using phpList And SES

Running a mailing list is not easy or cheap, but if you use AWS it can be. Find out how to create a low-cost and highly effective mailing list server.


Other Projects


Coursera Plus - Your Ticket To Success
18/07/2025

At the moment Coursera Plus has a special offer for new subscribers. If you love learning new skills or keeping your existing skills up to date, it's worth your immediate attention.



Human Programmer Outwits OpenAI's o3
23/07/2025

The 2025 AtCoder World Finals Heuristic Contest was billed a Human vs AI showdown. It is difficult to know which was the more important - that it was Psyho, a Polish human programmer, who to [ ... ]


More News

pico book

 

Comments




or email your comment to: comments@i-programmer.info



Last Updated ( Sunday, 06 October 2024 )