PrimMatrix.cs

using System;

namespace Algorithms.Graph.MinimumSpanningTree
{
    /// <summary>
    ///     Class that uses Prim's (Jarnik's algorithm) to determine the minimum
    ///     spanning tree (MST) of a given graph. Prim's algorithm is a greedy
    ///     algorithm that can determine the MST of a weighted undirected graph
    ///     in O(V^2) time where V is the number of nodes/vertices when using an
    ///     adjacency matrix representation.
    ///     More information: https://en.wikipedia.org/wiki/Prim%27s_algorithm
    ///     Pseudocode and runtime analysis: https://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm .
    /// </summary>
    public static class PrimMatrix
    {
        /// <summary>
        ///     Determine the minimum spanning tree for a given weighted undirected graph.
        /// </summary>
        /// <param name="adjacencyMatrix">Adjacency matrix for graph to find MST of.</param>
        /// <param name="start">Node to start search from.</param>
        /// <returns>Adjacency matrix of the found MST.</returns>
        public static float[,] Solve(float[,] adjacencyMatrix, int start)
        {
            ValidateMatrix(adjacencyMatrix);

            var numNodes = adjacencyMatrix.GetLength(0);

            // Create array to represent minimum spanning tree
            var mst = new float[numNodes, numNodes];

            // Create array to keep track of which nodes are in the MST already
            var added = new bool[numNodes];

            // Create array to keep track of smallest edge weight for node
            var key = new float[numNodes];

            // Create array to store parent of node
            var parent = new int[numNodes];

            for (var i = 0; i < numNodes; i++)
            {
                mst[i, i] = float.PositiveInfinity;
                key[i] = float.PositiveInfinity;

                for (var j = i + 1; j < numNodes; j++)
                {
                    mst[i, j] = float.PositiveInfinity;
                    mst[j, i] = float.PositiveInfinity;
                }
            }

            // Ensures that the starting node is added first
            key[start] = 0;

            // Keep looping until all nodes are in tree
            for (var i = 0; i < numNodes - 1; i++)
            {
                GetNextNode(adjacencyMatrix, key, added, parent);
            }

            // Build adjacency matrix for tree
            for (var i = 0; i < numNodes; i++)
            {
                if (i == start)
                {
                    continue;
                }

                mst[i, parent[i]] = adjacencyMatrix[i, parent[i]];
                mst[parent[i], i] = adjacencyMatrix[i, parent[i]];
            }

            return mst;
        }

        /// <summary>
        ///     Ensure that the given adjacency matrix represents a weighted undirected graph.
        /// </summary>
        /// <param name="adjacencyMatrix">Adjacency matric to check.</param>
        private static void ValidateMatrix(float[,] adjacencyMatrix)
        {
            // Matrix should be square
            if (adjacencyMatrix.GetLength(0) != adjacencyMatrix.GetLength(1))
            {
                throw new ArgumentException("Adjacency matrix must be square!");
            }

            // Graph needs to be undirected and connected
            for (var i = 0; i < adjacencyMatrix.GetLength(0); i++)
            {
                var connection = false;
                for (var j = 0; j < adjacencyMatrix.GetLength(0); j++)
                {
                    if (Math.Abs(adjacencyMatrix[i, j] - adjacencyMatrix[j, i]) > 1e-6)
                    {
                        throw new ArgumentException("Adjacency matrix must be symmetric!");
                    }

                    if (!connection && float.IsFinite(adjacencyMatrix[i, j]))
                    {
                        connection = true;
                    }
                }

                if (!connection)
                {
                    throw new ArgumentException("Graph must be connected!");
                }
            }
        }

        /// <summary>
        ///     Determine which node should be added next to the MST.
        /// </summary>
        /// <param name="adjacencyMatrix">Adjacency matrix of graph.</param>
        /// <param name="key">Currently known minimum edge weight connected to each node.</param>
        /// <param name="added">Whether or not a node has been added to the MST.</param>
        /// <param name="parent">The node that added the node to the MST. Used for building MST adjacency matrix.</param>
        private static void GetNextNode(float[,] adjacencyMatrix, float[] key, bool[] added, int[] parent)
        {
            var numNodes = adjacencyMatrix.GetLength(0);
            var minWeight = float.PositiveInfinity;

            var node = -1;

            // Find node with smallest node with known edge weight not in tree. Will always start with starting node
            for (var i = 0; i < numNodes; i++)
            {
                if (!added[i] && key[i] < minWeight)
                {
                    minWeight = key[i];
                    node = i;
                }
            }

            // Add node to mst
            added[node] = true;

            // Update smallest found edge weights and parent for adjacent nodes
            for (var i = 0; i < numNodes; i++)
            {
                if (!added[i] && adjacencyMatrix[node, i] < key[i])
                {
                    key[i] = adjacencyMatrix[node, i];
                    parent[i] = node;
                }
            }
        }
    }
}