Реализация алгоритма Краскала на С#

[Naf2000]

Красиво

Условия

else if (setA != null && setB != null)
{
if (setA != setB)

можно заменить на

else if (setA != setB)

[OkunevPY]

Нельзя, если SetA равен null код упадёт. Его надо проверить на null, а вот второе сравнение опустить и сразу сравнить с обектом.

Хотя с точки зрения статьи это лишннее, статья не про оптимальную реализацию алгоритма, а про реализацию как таковую. Поэтому все что можно расписать расписано, хотя это и кажеться излишним.

[dopusteam]

Там ж предыдущие if тогда отработают, нет?

[OkunevPY]

Да, их я упустил. Тогда вы правы, условие лишнее

[mayorovp]

Вот только алгоритм у вас некорретный: алгоритм Краскала работает за O(E log E), а ваш — за ϴ(EV²)!

В своей реализации вы совершенно упустили из виду, что система непересекающихся множеств — это вполне конкретный алгоритм, и надо реализовать именно его, а не то что вам подсказала левая пятка.

Под спойлером — правильная реализация (ну как правильная, могут быть ошибки, но алгоритм там правильный):

Скрытый текст

    class DisjointSets<T>
    {
        private readonly Dictionary<T, int> itemToIndex = new();
        private readonly List<int> parent = new();
        private readonly List<int> rank = new();

        /// <summary>
        /// Поиск номера корневого элемента множества для указанного элемента
        /// </summary>
        private int FindSet(T item)
        {
            if (!itemToIndex.TryGetValue(item, out int index))
            {
                // Элемента не было, создаём новое множество для него
                index = parent.Count;
                itemToIndex.Add(item, index);
                parent.Add(index);
                rank.Add(0);
                return index;
            }

            // Поиск корня в множестве 
            int set;
            for (set = index; parent[set] != set; set = parent[set]) ;

            // Эвристика сокращения путей
            while (index != set)
            {
                var p = parent[index];
                parent[index] = set;
                index = p;
            }

            return set;
        }

        /// <summary>
        /// Определяет лежат ли два элемента в одном множестве
        /// </summary>
        public bool IsInSameSet(T item1, T item2) => FindSet(item1) == FindSet(item2);

        /// <summary>
        /// Объединяет два множества
        /// </summary>
        public void Union(T item1, T item2)
        {
            var set1 = FindSet(item1);
            var set2 = FindSet(item2);

            if (set1 == set2) return;

            // Эвристика рангов
            if (rank[set1] > rank[set2])
                parent[set2] = set1;
            else if (rank[set1] < rank[set2])
                parent[set1] = set2;
            else
            {
                parent[set1] = set2;
                rank[set2]++;
            }
        }
    }

[mayorovp]

Теперь общие придирки к коду.

Первое. У вас вершина является просто строкой. Ну почему строка-то? В большинстве олимпиадных задач они кодируются числами, а в большинстве практических — являются внешними объектами. Так что тут или int пишите, или делайте дженерик по типу TVertex.

Второе. Вы сделали вершины сравниваемыми, но сравнение вершин по весу никому кроме вас не нужно. Зачем вообще раскрывать порядок сортировки алгоритма Краскала другим частям программы? Не говорю уже о том, что вы не согласовали CompareTo и Equals. Забудьте вы про IComparable<>, реализуйте лучше IComparer<>! Кода примерно столько же, а архитектурных проблем меньше.

Третье. У вас метод FindMinimumSpanningTree вышел "наполовину мутабельным": вы возвращаете новый граф, но при этом ещё и меняете старый (а именно, меняется порядок рёбер). Не то чтобы это было совсем-совсем плохо, но зачем так делать если этого можно очень легко избежать?

Пишем что-нибудь вроде foreach (Edge edge in _graph.OrderBy(e => e.EdgeWeight)) — и о чудо, нам даже компаратор из второго пункта не понадобился!

Четвёртое: наименованиe. Почему список рёбер графа называется _graph, а не _edges?

Пятое. У вас ToString за квадратичное время работает, научитесь уже использовать StringBuilder!