chatgpt MST Minimum Spanning Tree

Minimum Spanning Tree (MST) is a tree structure in graph theory that connects all nodes with the minimum possible total edge weight. It's used to find the optimal solution for a connected graph with non-negative edge weights to reach all nodes with the minimum total weight, used in various optimization problems. Common algorithms for finding MST are Kruskal's Algorithm and Prim's Algorithm.


Here is a simple implementation of Prim's algorithm for finding the minimum spanning tree in C#:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int[,] graph = new int[,] { { 0, 2, 0, 6, 0 },
                                    { 2, 0, 3, 8, 5 },
                                    { 0, 3, 0, 0, 7 },
                                    { 6, 8, 0, 0, 9 },
                                    { 0, 5, 7, 9, 0 } };

        int[] parent = new int[5];
        int[] key = new int[5];
        bool[] mstSet = new bool[5];

        for (int i = 0; i < 5; i++)
        {
            key[i] = int.MaxValue;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < 5 - 1; count++)
        {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < 5; v++)
                if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] < key[v])
                {
                    parent[v] = u;
                    key[v] = graph[u, v];
                }
        }

        Console.WriteLine("Edge \tWeight");
        for (int i = 1; i < 5; i++)
            Console.WriteLine(parent[i] + " - " + i + "\t" + graph[i, parent[i]]);
    }

    static int minKey(int[] key, bool[] mstSet)
    {
        int min = int.MaxValue, minIndex = -1;

        for (int v = 0; v < 5; v++)
            if (mstSet[v] == false && key[v] < min)
            {
                min = key[v];
                minIndex = v;
            }

        return minIndex;
    }
}

Note: This code uses an adjacency matrix representation of a graph.