#### Kruskal's Algorithm

using System;
using System.Collections.Generic;
using DataStructures.DisjointSet;

namespace Algorithms.Graph.MinimumSpanningTree;

/// <summary>
///     Algorithm to determine the minimum spanning forest of an undirected graph.
/// </summary>
/// <remarks>
///     Kruskal's algorithm is a greedy algorithm that can determine the
///     minimum spanning tree or minimum spanning forest of any undirected
///     graph. Unlike Prim's algorithm, Kruskal's algorithm will work on
///     graphs that are unconnected. This algorithm will always have a
///     running time of O(E log V) where E is the number of edges and V is
///     the number of vertices/nodes.
///     Pseudocode and analysis: https://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm .
/// </remarks>
public static class Kruskal
{
/// <summary>
///     Determine the minimum spanning tree/forest of the given graph.
/// </summary>
/// <returns>Adjacency matrix of the minimum spanning tree/forest.</returns>
{

var set = new DisjointSet<int>();
var nodes = new Node<int>[numNodes];
var edgeWeightList = new List<float>();
var nodeConnectList = new List<(int, int)>();

// Add nodes to disjoint set
for (var i = 0; i < numNodes; i++)
{
nodes[i] = set.MakeSet(i);
}

// Create lists with edge weights and associated connectivity
for (var i = 0; i < numNodes - 1; i++)
{
for (var j = i + 1; j < numNodes; j++)
{
{
}
}
}

var edges = Solve(set, nodes, edgeWeightList.ToArray(), nodeConnectList.ToArray());

// Initialize minimum spanning tree
var mst = new float[numNodes, numNodes];
for (var i = 0; i < numNodes; i++)
{
mst[i, i] = float.PositiveInfinity;

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

foreach (var (node1, node2) in edges)
{
}

return mst;
}

/// <summary>
///     Determine the minimum spanning tree/forest of the given graph.
/// </summary>
/// <returns>Adjacency list of the minimum spanning tree/forest.</returns>
public static Dictionary<int, float>[] Solve(Dictionary<int, float>[] adjacencyList)
{

var set = new DisjointSet<int>();
var nodes = new Node<int>[numNodes];
var edgeWeightList = new List<float>();
var nodeConnectList = new List<(int, int)>();

// Add nodes to disjoint set and create list of edge weights and associated connectivity
for (var i = 0; i < numNodes; i++)
{
nodes[i] = set.MakeSet(i);

{
}
}

var edges = Solve(set, nodes, edgeWeightList.ToArray(), nodeConnectList.ToArray());

// Create minimum spanning tree
var mst = new Dictionary<int, float>[numNodes];
for (var i = 0; i < numNodes; i++)
{
mst[i] = new Dictionary<int, float>();
}

foreach (var (node1, node2) in edges)
{
}

return mst;
}

/// <summary>
///     Ensure that the given graph is undirected.
/// </summary>
{
{
throw new ArgumentException("Matrix must be square!");
}

for (var i = 0; i < adj.GetLength(0) - 1; i++)
{
for (var j = i + 1; j < adj.GetLength(1); j++)
{
{
throw new ArgumentException("Matrix must be symmetric!");
}
}
}
}

/// <summary>
///     Ensure that the given graph is undirected.
/// </summary>
private static void ValidateGraph(Dictionary<int, float>[] adj)
{
for (var i = 0; i < adj.Length; i++)
{
{
{
throw new ArgumentException("Graph must be undirected!");
}
}
}
}

/// <summary>
///     Determine the minimum spanning tree/forest.
/// </summary>
/// <param name="set">Disjoint set needed for set operations.</param>
/// <param name="nodes">List of nodes in disjoint set associated with each node.</param>
/// <param name="edgeWeights">Weights of each edge.</param>
/// <param name="connections">Nodes associated with each item in the <paramref name="edgeWeights"/> parameter.</param>
/// <returns>Array of edges in the minimum spanning tree/forest.</returns>
private static (int, int)[] Solve(DisjointSet<int> set, Node<int>[] nodes, float[] edgeWeights, (int, int)[] connections)
{
var edges = new List<(int, int)>();

Array.Sort(edgeWeights, connections);

foreach (var (node1, node2) in connections)
{
if (set.FindSet(nodes[node1]) != set.FindSet(nodes[node2]))
{
set.UnionSet(nodes[node1], nodes[node2]);