ОСТОРОЖНО МОШЕННИКИ! В последнее время в соиальных сетях учстились случаи педложения помощи в написании прогамм от лиц, прикрвающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в псторонних группах ВК. Для связи с нами используйте исключительно эти контакт: vscoderu@yandex.ru, https://vk.com/vscode


Алгоритм Прима на C#


Рассмотрим алгоритм Прима. Он используется для построения минимального остовного дерева на связном неориентированном графе. Будет приведено описание алгоритма и его реализация на языке программирования C#.

Алгоритм Прима — это алгоритм поиска минимального остовного дерева связного взвешенного неориентированного графа. Был открыт Робертом Примом в 1957 году.

Вес ребра — числовое значение, поставленное в соответствие данному ребру графа. Вес ребра можно интерпретировать как длину ребра.

Взвешенный граф — граф, для каждого ребра которого задан вес.

Связный граф — это такой граф, в котором из любой его вершины можно попасть в любую другую вершину.

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

Описание алгоритма Прима

На входе имеется взвешенный связный неориентированный граф.

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

На выходе имеем минимальное остовное дерево.

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

Алгоритм Прима. Демонстрация работы - vscode.ru

Шаг 1. Выберем произвольную вершину. Пусть это будет вершина номер 3. Ей инцидентны ребра (с неиспользованными вершинами): b(3), c(1), d(4). Ребро с наименьшим весом — c. Включим его и инцидентную ему вершину в дерево.

Алгоритм Прима. Демонстрация работы - vscode.ru

Шаг 2. Вершинам 1 и 3 инцидентны ребра (с неиспользованными вершинами): a(5), b(3), d(4), f(2). Ребро с наименьшим весом — f. Включим его и инцидентную ему вершину в дерево.


Алгоритм Прима. Демонстрация работы - vscode.ru

Шаг 3. Вершинам 1, 3 и 5 инцидентны ребра (с неиспользованными вершинами): a(5), b(3), d(4), e(11). Ребро с наименьшим весом — b. Включим его и инцидентную ему вершину в дерево.

Алгоритм Прима. Демонстрация работы - vscode.ru

Шаг 4. Вершинам 1, 2, 3 и 5 инцидентны ребра (с неиспользованными вершинами): d(4) и e(11). Ребро с наименьшим весом — d. Включим его и инцидентную ему вершину в дерево.

Алгоритм Прима. Демонстрация работы - vscode.ru

Все вершины графа включены в дерево. Работа алгоритма завершена.

Реализация алгоритма

Пусть ребро графа представлено экземпляром класса Edge:

, где v1 и v2 — номера вершин (нумерация вершин начинается с нуля), инцидентных ребру, а weight  — вес ребра.

А все ребра графа пусть представлены в виде списка:

Приведем реализацию алгоритма Прима на языке C#.

Аргументы метода algorithmByPrimnumberV — количество вершин в исходном графе, E — список ребер исходного графа, MST — список, в который будут занесены ребра, составляющие минимальное остовное дерево.

Кратко опишем работу метода algorithmByPrim(). В начале инициализируются списки с данными: ребра, не включенные в дерево, вершины, включенные в дерево, и вершины, не включенные в дерево (строки 4-10). Затем выбирается случайная начальная вершина, с которой начнется построение минимального остовного дерева (строки 12-14). Цикл while будет продолжаться до тех пор, пока все вершины графа не будут включены в дерево (15-47). На каждой итерации цикла выполняется следующее:

  1. Производится поиск ребра с наименьшим весом, один конец которого — это вершина, входящая в дерево, а другой — нет (строки 19-32).
  2. Вершина, инцидентная найденному ребру, заносится в список использованных и удаляется из списка неиспользованных (строки 34-43).
  3. Найденное ребро заносится в список ребер, составляющих дерево, и удаляется из списка неиспользованных ребер (строки 45-46).

Перед вызовом метода algorithmByPrim(), необходимо создать список, в котором будут хранится ребра, составляющие минимальное остовное дерево:

Скачать код метода algorithmByPrim

 

 

4.3/5 - (40 голосов)



Поделиться в соц. сетях:

5 комментария(ев) к статье “Алгоритм Прима на C#

    1. admin Автор статьи

      Здравствуйте! Да, есть готовая программа, реализующая алгоритм Прима на C#, Windows Forms.

      Можем предоставить видео с демонстрацией программы. Если Вас программа устроит, то можете ее купить. 200р.

          1. Кирилл

            А можно и мне тоже готовую программу, спасибо.

Добавить комментарий

Ваш адрес email не будет опубликован.