В данной статье для реализации алгоритма будут рассмотрены:

  1. Система хранения графа на основе List<>

  2. Сортировка рёбер графа по весу

  3. Система непересекающихся множеств


Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.

О чём речь?

Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.

На первом рисунке можно увидеть граф. Если мы соединим все его вершины без образования циклов, то получим остовное дерево этого графа. Примеры остовных деревьев выделены цветом на втором и третьем рисунках.

Теперь наделим рёбра нашего графа весом.

И речь уже будет идти о минимальном остовном дереве графа. Если мы имеем несколько вариантов остовных деревьев, минимальным из них будет считаться то, сумма веса всех рёбер которого меньше остальных.

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

План действий

  1. Сортируем имеющиеся рёбра по весу.

  2. Создаём новое множество и добавляем в него первое ребро.

  3. Затем пытаемся добавить каждое новое ребро в имеющееся множество, если возникает цикл - пропускаем.

  4. Итоговое множество рёбер и есть искомое минимальное остовное дерево.

По сути, это и есть формулировка алгоритма Краскала. Звучит совсем просто.

Самый весёлый пункт из имеющихся - третий. Потому что проверка на появление циклов на каждом шаге будет не сильно простым занятием. Его мы модифицируем при помощи системы непересекающихся множеств.

Но для начала давайте рассмотрим систему хранения графа в программе с использованием List<>. Если перед вами стоит задача неиспользования любых структур данных, кроме собственных, в этом репозитории вы найдёте нужную реализацию. Сам алгоритм в ней отличается незначительно.

Система хранения графа

Что есть граф? По сути - совокурность вершин и соединяющих их рёбер. Но ведь если помимо веса хранить о каждом ребре информацию о том, какие вершины оно соединяет, для помещения целого графа в память компьютера нам хватит списка рёбер, в него входящих.

Именно поэтому граф в этой реализации представлен дженерик листом рёбер.

Структура ребра и IComparable

Ниже можно увидеть структуру ребра: всё то, о чём было сказано выше. Вес и две вершины, представленные свойствами.

    public class Edge : IComparable<Edge>
    {
        public int EdgeWeight { get; set; }
        public string VertexA { get; set; }
        public string VertexB { get; set; }

        public Edge(string vertexA, string vertexB, int weight)
        {
            VertexA = vertexA;
            VertexB = vertexB;
            EdgeWeight = weight;
        }

        public int CompareTo(Edge other)
        {
            if (other == null) return 1;
            return EdgeWeight.CompareTo(other.EdgeWeight);
        }
    }

Класс реализует интерфейс IComparable с целью упростить сортировку рёбер графа, а именно - не изобретать велосипед и просто использовать стандартную сортировку для листа.

Далее рассмотрим по частям класс Graph.

Структура и основные методы класса Graph

Для удобства работы он реализует IEnumerable<Edge>.
public class Graph : IEnumerable<Edge>
{
    //код класса
    public IEnumerator<Edge> GetEnumerator()
    {
        return _graph.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _graph.GetEnumerator();
    }
}

В основе класса лежит List<Edge>, то есть список рёбер.

private List<Edge> _graph;

public Graph()
{
      _graph = new List<Edge>();
}

public Graph(Edge val)
{
     Edge[] value = new Edge[] { val };

     _graph = new List<Edge>(value);
}

Два конструктора облегчат работу с данным классом.

Далее можно увидеть несколько вспомогательных методов, таких как добавление в конец графа одного ребра и слияние графов. Последнему стоит уделить внимание.

Используя цикл foreach (да-да, именно для него нам пригодилась реализация интерфейса IEnumerable<Edge>) мы проходим по всем рёбрам второго графа и добавляем их к первому.

public void Add(Graph graph)
{
      foreach (Edge edge in graph)
      {
           _graph.Add(edge);
      }
}

public void Add(Edge edge)
{
     _graph.Add(edge);
}

Это основа, но без неё никуда.

Перейдём к более важным для вывода информации методам класса.

public int GetWeight()
{
			int weight = 0;
      foreach (Edge edge in _graph)
      {
           weight += edge.EdgeWeight;   
      }
      return weight;
}

Метод GetWeight() даёт нам возможность подсчёта суммарного веса графа.

public override string ToString()
{
      string result = string.Empty;

      foreach (Edge edge in _graph)
      {
           result += $"{edge.VertexA} {edge.VertexB} {edge.EdgeWeight}\n";
      }

      return result;
}

Переопределяем метод ToString() мы с целью красивого вывода графа.

На этом базовые методы класса Graph заканчиваются.

Сортировка рёбер графа по весу.

А теперь приятный сюрприз. Всё, что нам нужно для сортировки рёбер по весу - эти четыре строчки.

public void Sort()
{
     _graph.Sort();
}

Потому что класс рёбер реализует IComparable.

Система непересекающихся множеств

Данный вариант реализации далёк от оригинала, однако проще для восприятия.

Структура множеств

Каждое множество будет представлено классом Set с собственным графом и списком вершин, в оный входящих.

На рисунке выше можно увидеть уже знакомый граф и представление системы непересекающихся множеств после первых шагов алгоритма Краскала, а именно:

Выбрали минимальное ребро: 5-4 веса 4.
 Добавили его в граф множества. 
Вершины 5 и 4, соединяемые им, добавили в лист вершин множества. 

Выбрали минимальное ребро из оставшихся: 4-3 веса 5. 
Добавили его в граф множества. 
Вершину 3 добавили в лист вершин множества. Вершина 4 уже там была.

Именно так хранится информация в множествах.
На рисунке выше можно увидеть уже знакомый граф и представление системы непересекающихся множеств после первых шагов алгоритма Краскала, а именно: Выбрали минимальное ребро: 5-4 веса 4. Добавили его в граф множества. Вершины 5 и 4, соединяемые им, добавили в лист вершин множества. Выбрали минимальное ребро из оставшихся: 4-3 веса 5. Добавили его в граф множества. Вершину 3 добавили в лист вершин множества. Вершина 4 уже там была. Именно так хранится информация в множествах.

Отдельный лист вершин нужен нам для проверки на цикл в дальнейшем.

Переведём в код описанное выше:

 public class Set
 {
        public Graph SetGraph;
        public List<string> Vertices;

        public Set(Edge edge)
        {
            SetGraph = new Graph(edge);

            Vertices = new List<string>();
            Vertices.Add(edge.VertexA);
            Vertices.Add(edge.VertexB);
        }
   //методы класса
 }

Для работы с системой множеств нам понадобится ряд методов:

  1. Объединение двух множеств, слияние. Здесь мы к имеющемуся множеству добавляем другое с использованием соединяющего ребра.

  2. Добавление ребра к имеющемуся множеству.

  3. Проверка наличия вершины в списке Vertices.

public void Union(Set set, Edge connectingEdge)
{
      SetGraph.Add(set.SetGraph);
      Vertices.AddRange(set.Vertices);
      SetGraph.Add(connectingEdge);
}

public void AddEdge(Edge edge)
{
      SetGraph.Add(edge);
      Vertices.Add(edge.VertexA);
      Vertices.Add(edge.VertexB);
}

public bool Contains(string vertex)
{
      return Vertices.Contains(vertex);
}

Класс системы непересекающихся множеств

Рассмотрим класс, являющийся местом хранения всех имеющихся множеств и своего рода прослойкой, позволяющей добавить ребро в одно из множеств или решить, что оно никогда не займёт в них своё место.

class SystemOfDisjointSets
    {
        public List<Set> Sets;

        public void AddEdgeInSet(Edge edge)
        {
            //Здесь переданное ребро найдёт свое место в одном из множеств 
          	//или не войдёт в остовное дерево.
        }

        public Set Find(string vertex)
        {
            foreach (Set set in Sets)
            {
                if (set.Contains(vertex)) return set;
            }
            return null;
        }
    }

Метод Find принимает вершину графа и возвращает множество, к которому она принадлежит, или null, если такое множество не найдено.

Далее по шагам напишем метод public void AddEdgeInSet(Edge edge).

Разбиение графа на множества

Суть метода в том, что мы проходимся по всем рёбрам и проверяем, принадлежат ли стягиваемые ими вершины какому-либо множеству. Далее возможны четыре случая. Для наглядности изобразим их на схеме:

SetA - множество, в котором находится вершина А, 
SetB - множество, в котором находится вершина B. 
+ - вершина принадлежит какому-то множеству, 
null - вершина не принадлежит множеству.
SetA - множество, в котором находится вершина А, SetB - множество, в котором находится вершина B. + - вершина принадлежит какому-то множеству, null - вершина не принадлежит множеству.

Осталось записать полученные варианты на С#:

public void AddEdgeInSet(Edge edge)
{
      Set setA = Find(edge.VertexA);
      Set setB = Find(edge.VertexB);

      if (setA != null && setB == null)
      {
           setA.AddEdge(edge);
      }
      else if (setA == null && setB != null)
      {
          setB.AddEdge(edge);
      }
      else if (setA == null && setB == null)
      {
           Set set = new Set(edge);
           Sets.Add(set);
      }
      else if (setA != null && setB != null)
      {
           if (setA != setB)
           {
                setA.Union(setB, edge);
                Sets.Remove(setB);
           }
      }
}

Алгоритм Краскала: объединим полученные механизмы

Теперь мы с чистой совестью можем записать алгоритм Краскала в классе Graph как метод FindMinimumSpanningTree.

Всё по пунктам, известным нам заранее:

  1. Сортируем рёбра графа по возрастанию веса.

  2. Используя систему непересекающихся множеств разбиваем граф на множества до тех пор, пока не останется лишь один Set. Он останется один гарантированно, если граф был связный.

  3. Возвращаем минимальное остовное дерево, оно же - граф единственного оставшегося сета. (Для Find - using System.LINQ)

public Graph FindMinimumSpanningTree()
{
     Sort();
     var disjointSets = new SystemOfDisjointSets();
     foreach (Edge edge in _graph)
     {
          disjointSets.AddEdgeInSet(edge);
     }

     return disjointSets.Sets.First().SetGraph;
}

На этом алгоритм закончен, в репозитории также есть пример работы и удобного считывания графа из консоли, однако к теме статьи это не относится, поэтому не буду удлинять и без того обёмный текст.

Спасибо за внимание, надеюсь, что информация была полезной.

Комментарии (6)


  1. Naf2000
    23.01.2022 09:34
    +3

    Красиво

    Условия

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

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

    else if (setA != setB)


    1. OkunevPY
      23.01.2022 10:27

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

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


      1. dopusteam
        23.01.2022 10:30
        +1

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


        1. OkunevPY
          23.01.2022 13:54

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


  1. mayorovp
    23.01.2022 12:39
    +5

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


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


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


    Скрытый текст
        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]++;
                }
            }
        }


  1. mayorovp
    23.01.2022 13:00
    +8

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


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


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


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


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


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


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