Реализация алгоритма Краскала на С#
В данной статье для реализации алгоритма будут рассмотрены:
Система хранения графа на основе List<>
Сортировка рёбер графа по весу
Система непересекающихся множеств
Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.
Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.
Теперь наделим рёбра нашего графа весом.
И речь уже будет идти о минимальном остовном дереве графа. Если мы имеем несколько вариантов остовных деревьев, минимальным из них будет считаться то, сумма веса всех рёбер которого меньше остальных.
На просторах интернета есть множество ресурсов, посвященных данному алгоритму, однако все варианты реализации, встреченные мной, показались слишком сложными для понимания и использования. Хочу предложить более приближенный к реальности вариант. Для удобства оставляю ссылку на репозиторий с полной реализацией и примерами.
План действий
Сортируем имеющиеся рёбра по весу.
Создаём новое множество и добавляем в него первое ребро.
Затем пытаемся добавить каждое новое ребро в имеющееся множество, если возникает цикл — пропускаем.
Итоговое множество рёбер и есть искомое минимальное остовное дерево.
По сути, это и есть формулировка алгоритма Краскала. Звучит совсем просто.
Самый весёлый пункт из имеющихся — третий. Потому что проверка на появление циклов на каждом шаге будет не сильно простым занятием. Его мы модифицируем при помощи системы непересекающихся множеств.
Но для начала давайте рассмотрим систему хранения графа в программе с использованием List<>. Если перед вами стоит задача неиспользования любых структур данных, кроме собственных, в этом репозитории вы найдёте нужную реализацию. Сам алгоритм в ней отличается незначительно.
Система хранения графа
Что есть граф? По сути — совокурность вершин и соединяющих их рёбер. Но ведь если помимо веса хранить о каждом ребре информацию о том, какие вершины оно соединяет, для помещения целого графа в память компьютера нам хватит списка рёбер, в него входящих.
Именно поэтому граф в этой реализации представлен дженерик листом рёбер.
Структура ребра и IComparable
Ниже можно увидеть структуру ребра: всё то, о чём было сказано выше. Вес и две вершины, представленные свойствами.
Класс реализует интерфейс IComparable с целью упростить сортировку рёбер графа, а именно — не изобретать велосипед и просто использовать стандартную сортировку для листа.
Далее рассмотрим по частям класс Graph.
Структура и основные методы класса Graph
В основе класса лежит List<Edge>, то есть список рёбер.
Два конструктора облегчат работу с данным классом.
Используя цикл foreach (да-да, именно для него нам пригодилась реализация интерфейса IEnumerable<Edge>) мы проходим по всем рёбрам второго графа и добавляем их к первому.
Это основа, но без неё никуда.
Перейдём к более важным для вывода информации методам класса.
Метод GetWeight() даёт нам возможность подсчёта суммарного веса графа.
Переопределяем метод ToString() мы с целью красивого вывода графа.
На этом базовые методы класса Graph заканчиваются.
Сортировка рёбер графа по весу.
А теперь приятный сюрприз. Всё, что нам нужно для сортировки рёбер по весу — эти четыре строчки.
Потому что класс рёбер реализует IComparable.
Система непересекающихся множеств
Данный вариант реализации далёк от оригинала, однако проще для восприятия.
Структура множеств
Каждое множество будет представлено классом Set с собственным графом и списком вершин, в оный входящих.
На рисунке выше можно увидеть уже знакомый граф и представление системы непересекающихся множеств после первых шагов алгоритма Краскала, а именно: Выбрали минимальное ребро: 5-4 веса 4. Добавили его в граф множества. Вершины 5 и 4, соединяемые им, добавили в лист вершин множества. Выбрали минимальное ребро из оставшихся: 4-3 веса 5. Добавили его в граф множества. Вершину 3 добавили в лист вершин множества. Вершина 4 уже там была. Именно так хранится информация в множествах.
Отдельный лист вершин нужен нам для проверки на цикл в дальнейшем.
Переведём в код описанное выше:
Для работы с системой множеств нам понадобится ряд методов:
Класс системы непересекающихся множеств
Рассмотрим класс, являющийся местом хранения всех имеющихся множеств и своего рода прослойкой, позволяющей добавить ребро в одно из множеств или решить, что оно никогда не займёт в них своё место.
Метод Find принимает вершину графа и возвращает множество, к которому она принадлежит, или null, если такое множество не найдено.
Далее по шагам напишем метод public void AddEdgeInSet(Edge edge).
Разбиение графа на множества
Суть метода в том, что мы проходимся по всем рёбрам и проверяем, принадлежат ли стягиваемые ими вершины какому-либо множеству. Далее возможны четыре случая. Для наглядности изобразим их на схеме:
SetA — множество, в котором находится вершина А, SetB — множество, в котором находится вершина B. + — вершина принадлежит какому-то множеству, null — вершина не принадлежит множеству.
Осталось записать полученные варианты на С#:
Алгоритм Краскала: объединим полученные механизмы
Теперь мы с чистой совестью можем записать алгоритм Краскала в классе Graph как метод FindMinimumSpanningTree.
Всё по пунктам, известным нам заранее:
Сортируем рёбра графа по возрастанию веса.
Используя систему непересекающихся множеств разбиваем граф на множества до тех пор, пока не останется лишь один Set. Он останется один гарантированно, если граф был связный.
Возвращаем минимальное остовное дерево, оно же — граф единственного оставшегося сета. (Для Find — using System.LINQ)
На этом алгоритм закончен, в репозитории также есть пример работы и удобного считывания графа из консоли, однако к теме статьи это не относится, поэтому не буду удлинять и без того обёмный текст.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Программа для построения графов C#
Представляем вашему вниманию программу для построения графов, написанную на языке C#. Внизу страницы вы можете скачать исходник этой программы, а в этой статье будут описаны функции программы и основные приемы, использовавшиеся при их кодировании.
Структура пользовательского интерфейса
Рисунок 1. Пользовательский интерфейс программы
Пользовательский интерфейс программы изображен на рисунке 1. На нем цифрами обозначены элементы управления:
- Выбор вершины (при выборе какой-либо вершины, отображается ее степень).
- Создание вершины.
- Создание ребра.
- Удаление элемента.
- Удаление всего графа.
- Рабочее поле для построения графа.
- Построение матрицы смежности.
- Построение матрицы инцидентности.
- Поле для вывода информации о графе: степень выбранной вершины, матриц смежности и инцидентности, элементарных цепей и циклов.
- Вывод всех элементарных цепей.
- Вывод всех элементарных циклов.
- Информация о программе (окно представлено на рисунке 2).
- Сохранение изображения графа.
Если при построении ребра вы выбрали не ту вершину, то отменить выбор можно, нажав правой кнопкой мыши на выбранной вершине.
Рисунок 2. Окно «О программе»
Описание структуры программы
Опишем ключевые моменты в программном коде.
При кодировании граф был представлен в виде списка (List<>) экземпляров класса Vertex (вершина):
где x и y — координаты центра вершины.
И списка (List<>) экземпляров класса Edge (ребро):
v1 и v2 — номера вершин, которые соединяет ребро.
Когда происходит выбор вершины мышью, поиск нужной вершины из списка осуществляется посредством перебора всех вершин и проверки условия принадлежности точки, в месте щелчка мыши, окружности вершины с помощью уравнения окружности: (x — x0) 2 + (y — y0) 2 = R 2 .
где e.X, e.Y — координаты точки в месте щелчка мыши, а G.R — радиус окружности вершины.
Заполнение матрицы смежности:
numberV — количество вершин в графе. matrix имеет размер [numberV, numberV].
Заполнение матрицы инцидентности:
где numberV — количество вершин в графе. matrix имеет размер [numberV, E.Count].
Определение степени вершины происходит в результате суммирования элементов строки матрицы смежности с номером, равным номеру выбранной вершины.
Если нажата кнопка «удаление элемента», то при щелчке мышью на рабочем поле происходит перебор всех элементов графа и поиск элемента, которому принадлежит координата в месте щелчка. При этом для ребер и петель поиск осуществляется с допуском в несколько пикселей, то есть, например, принадлежность точки, в месте щелка, конкретному ребру характеризуется принадлежностью точки области, границами которой выступают прямые, отстоящие вверх и вниз от исходной прямой на несколько пикселей.
Проиллюстрировать вышесказанное можно с помощью рисунка:
Рисунок 3. Области, рассматриваемые при поиске элемента графа для удаления
Красным цветом обозначен тот самый допуск в несколько пикселей при поиске элемента для удаления. Для вершины никакого допуска рассматривать не нужно.
Про поиск элементарных цепей и циклов мы уже рассказывали на vscode.ru. Почитать можно здесь:
Скачать исходник программы, написанной в Visual Studio, можно, нажав на кнопку ниже.
Реализация Graph на C++ с использованием STL
Учитывая неориентированный или ориентированный граф, реализуйте структуру данных Graph на C++ с использованием STL. Реализуйте как взвешенные, так и невзвешенные графы, используя представление списка смежности Graph.
Условие:
Как мы уже знаем, список смежности связывает каждую вершину Graph с набором соседних вершин или ребер, т. е. каждая вершина хранит список смежных вершин. Существует множество вариантов представления списка смежности в зависимости от реализации.
Например, ниже представлен список смежности приведенного выше Graph:
Приведенное выше представление позволяет хранить дополнительные данные о вершинах, но практически очень эффективно, когда граф содержит только несколько ребер. Мы будем использовать векторный класс STL для реализации представления Graph в виде списка смежности.
Что такое граф, классификация графов, реализация на C++
Что такое граф, классификация графов, реализация на C++
Граф – совокупность точек, соединенных линиями. Точки называются вершинами , или узлами , а линии – ребрами , или дугами .
Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.
Граф, содержащий ребра между всеми парами вершин, является полным .
Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами , а это значение – весом ребра .
Когда у ребра оба конца совпадают, т.е. оно выходит из вершины и входит в нее, то такое ребро называется петлей .
Классификация графов
Графы делятся на
- связные
- несвязные
В связном графе между любой парой вершин существует как минимум один путь.
В несвязном графе существует хотя бы одна вершина, не связанная с другими.
Графы также подразделяются на
- ориентированные
- неориентированные
- смешанные
В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.
Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.
Способы представления графа
Граф может быть представлен (сохранен) несколькими способами:
- матрица смежности;
- матрица инцидентности;
- список смежности (инцидентности);
- список ребер.
Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.
- 0 – соответствует отсутствию ребра,
- 1 – соответствует наличию ребра.
Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.
В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.
Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.
Список смежности (инцидентности)
Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк — не больше, чем вершин в графе.
В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины.
Преимущества списка смежности:
- Рациональное использование памяти.
- Позволяет быстро перебирать соседей вершины.
- Позволяет проверять наличие ребра и удалять его.
Недостатки списка смежности:
- При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.
- Нет быстрого способа проверить, существует ли ребро между двумя вершинами.
- Количество вершин графа должно быть известно заранее.
- Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:
- номер вершины, с которой соединяется текущая;
- вес ребра.
Список рёбер
В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).
Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер.
Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными , с малым — разреженными . Плотные графы удобнее хранить в виде матрицы смежности, разреженные — в виде списка смежности.
Алгоритмы обхода графов
Основными алгоритмами обхода графов являются
- Поиск в ширину
- Поиск в глубину
Поиск в ширину подразумевает поуровневое исследование графа:
- вначале посещается корень – произвольно выбранный узел,
- затем – все потомки данного узла,
- после этого посещаются потомки потомков и т.д.
Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:- 0 — оранжевый – необнаруженная вершина;
- 1 — зеленый – обнаруженная, но не посещенная вершина;
- 2 — серый – обработанная вершина.
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в ширину
- Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном).
- Поиск компонент связности.
- Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов.
- Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
- Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.Реализация на C++ (с использованием очереди STL)
Результат выполнения
Задача поиска кратчайшего пути
Реализация на С++Результат выполнения
Поиск в глубину – это алгоритм обхода вершин графа.
Поиск в ширину производится симметрично (вершины графа просматривались по уровням). Поиск в глубину предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность продвижения означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина).
Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:
- все вершины графа уже просмотрены,
- просмотрены вершины доступные из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант).
Каждая вершина может находиться в одном из 3 состояний:
- 0 — оранжевый – необнаруженная вершина;
- 1 — зеленый – обнаруженная, но не посещенная вершина;
- 2 — серый – обработанная вершина;
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в глубину
- Поиск любого пути в графе.
- Поиск лексикографически первого пути в графе.
- Проверка, является ли одна вершина дерева предком другой.
- Поиск наименьшего общего предка.
- Топологическая сортировка.
- Поиск компонент связности.
Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.
Для реализации алгоритма удобно использовать стек или рекурсию.Реализация на C++ (с использованием стека STL)
Результат выполнения
Задача поиска лексикографически первого пути на графе.
Реализация на C++Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.
Реализация обхода графа в глубину на C++ (с использованием рекурсии)