Tag: easy

Minimum Spanning Tree – Kruskal Algorithm – C# Implementation

using System.Collections.Generic;
using System.Linq;

public static class KruskalAlgorithm
{
    public static List<Edge> Kruskal(int numberOfVertices, List<Edge> edges)
    {
        // Inital sort
        edges.Sort();

        // Set parents table
        var parent = Enumerable.Range(0, numberOfVertices).ToArray();
            
        // Spanning tree list
        var spanningTree = new List<Edge>();
        foreach (var edge in edges)
        {
            var startNodeRoot = FindRoot(edge.StartNode, parent);
            var endNodeRoot = FindRoot(edge.EndNode, parent);

            if (startNodeRoot != endNodeRoot)
            {
                // Add edge to the spanning tree
                spanningTree.Add(edge);

                // Mark one root as parent of the other
                parent[endNodeRoot] = startNodeRoot;
            }
        }

        // Return the spanning tree
        return spanningTree;
    }

    private static int FindRoot(int node, int[] parent)
    {
        var root = node;
        while (root != parent[root])
        {
            root = parent[root];
        }

        while (node != root)
        {
            var oldParent = parent[node];
            parent[node] = root;
            node = oldParent;
        }

        return root;
    }
}

How to generate Permutations without repetition recursively in C#

using System;

class GroupPermutations
{
    static void Main(string[] args)
    {
        string[] array = { "apple", "peach", "orange" };
        Perm(array, 0);
    }

    static void Perm<T>(T[] arr, int k)
    {
        if (k >= arr.Length)
            Print(arr);
        else
        {
            Perm(arr, k + 1);
            for (int i = k + 1; i < arr.Length; i++)
            {
                Swap(ref arr[k], ref arr[i]);
                Perm(arr, k + 1);
                Swap(ref arr[k], ref arr[i]);
            }
        }
    }

    private static void Swap<T>(ref T item1, ref T item2)
    {
        T temp = item1;
        item1 = item2;
        item2 = temp;
    }

    private static void Print<T>(T[] arr)
    {
        Console.WriteLine("{" + string.Join(", ", arr) + "}");
    }
}

//Result:
//{apple, peach, orange}
//{apple, orange, peach}
//{peach, apple, orange}
//{peach, orange, apple}
//{orange, peach, apple}
//{orange, apple, peach}