Remkomplekty.ru

IT Новости из мира ПК
5 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Алгоритм краскала паскаль

Алгоритм краскала паскаль

страницы: 1 2 3 4 5 6

Содержание

Итеративный алгоритм

Сравнение алгоритмов КомпСвяз-Рек и КомпСвяз-Итер

В худшем случае (при полном графе) рекурсивный алгоритм, перебирая все возможные ребра, будет вынужден вызвать основную процедуру (N — 1)! раз. Велика вероятность, что при достаточно большом N произойдёт переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной матрицы смежности дают сильное ограничение на возможное количество вершин графа: не более 250 (см. лекцию 3 ).

Итеративный же алгоритм переберёт все рёбра графа, которых может быть не более, чем N*(N+1)/2 . В половине этих случаев возможна ситуация объединения двух компонент связности в одну, для чего потребуется ещё N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N 3 /8 . Возможное количество вершин графа ограничено только максимальным размером линейного массива ( 32 000 ).

Нахождение минимального каркаса

Задача. В заданном взвешенном связном графе определить множество рёбер, составляющих некоторый его оптимальный каркас (например, минимальный по сумме весов входящих в него рёбер).

Рекурсивный алгоритм

Алгоритм Каркас–Рек

Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во–первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во–вторых, чтобы в каркасе было ровно N-1 ребро 1 ( N — количество вершин графа).

Реализация

procedure step (v , k : Byte ; r : LongInt ) ;
var j : Byte ;
begin
if r 0 ) and (mark[j] = 0 ) then
begin
mark[j] := 1 ;
step(j , k + 1 , r + sm[v , j]) ;
mark[j] := 0
end ;
end ;

begin
<. >
for i := 1 to N do
mark[i] := 0 ;
min := MaxLongInt ;
for i := 1 to N do
begin
mark[i] := 1 ;
step(i , 1 , 0 ) ;
mark[i] := 0 ;
end ;
WriteLn ( min ) ;
<. >
end .

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

Итеративный алгоритм

Алгоритм Краскала
  1. Упорядочить все рёбра графа по возрастанию их весов.
  2. Применить алгоритм КомпСвяз–Итер (см. пункт «Подсчёт количества компонент связности»).

Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено ( N-1 )–е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).

Реализация

Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз–Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчёт добавленных в каркас рёбер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счётчик добавленных рёбер станет равным N-1 .

Нахождение кратчайших путей

Задача. В заданном взвешенном связном графе найти расстояние (длину кратчайшего пути) от выделенной вершины s до вершины t . Веса всех рёбер строго положительны.

Рекурсивный алгоритм

Алгоритм Расст–Рек

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

Реализация

Пусть граф задан матрицей смежности sm , а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути «на возврате» совершается рекурсией автоматически, поскольку в её заголовке использован параметр–значение, а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром–значением чересчур накладно:

procedure rasst (v : Byte ; r : LongInt ) ;
var i : Byte ;
begin
if v = t then
begin
if r 0 ) then
begin
mark[i] := 1 ;
rasst(i , r + sm[v , i]) ;
mark[i] := 0
end
end ;

begin
<. >
for i := 1 to N do
mark[i] := 0 ;
min := MaxLongInt ;
mark[s] := 1 ;
rasst(s , 0 ) ;
mark[s] := 0 ;
<. >
end .

Итеративный алгоритм

Алгоритм , предложенный Дейкстрой 2 , настолько мощнее рекурсивного алгоритма Расст–Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t , но и до всех остальных вершин графа.

Итак, пусть граф задан матрицей смежности.

Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt , символизирующими «бесконечность». По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.

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

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

Алгоритм Дейкстры

Расстояние от s до s , конечно же, равно 0 . Кроме того, это расстояние уже никогда не сможет стать меньше — ведь веса всех рёбер графа у нас положительны. Таким образом:

Повторить N-1 раз следующие действия:

для всех непомеченных вершин х , связанных ребром с вершиной last , необходимо пересчитать расстояние:

  1. среди всех непомеченных вершин найти минимум в массиве dist : это будет новая вершина last ;
  2. пометить эту новую вершину в массиве done .
Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел min , использованную в тексте программы, читатели смогут написать самостоятельно.

Сравнение алгоритмов Расст–Рек и Дейкстры

Сложность рекурсивного алгоритма пропорциональна N! , а алгоритм Дейкстры имеет сложность

Алгоритм Краскала

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

Как работает алгоритм Краскала

Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.

Читать еще:  Вывод массива паскаль

Мы начинаем с ребер с наименьшим весом и продолжаем добавлять ребра, пока не достигнем нашей цели.

Шаги для реализации алгоритма Краскала следующие:

  1. Сортировать все ребра от малого веса до высокого.
  2. Возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавление ребра создало цикл, то отклоните это ребро.
  3. Продолжайте добавлять ребра, пока не достигнете всех вершин.

Пример алгоритма Краскала

Алгоритм Краскала. Псевдокод.

Любой минимальный алгоритм остовного дерева вращается вокруг проверки, создает ли ребро цикл или нет.

Наиболее распространенный способ выяснить это — алгоритм Union FInd . Алгоритм Union-Find разделяет вершины на кластеры и позволяет нам проверить, принадлежат ли две вершины одному кластеру или нет, и, следовательно, решить создает ли добавление ребра цикл.

Реализация алгоритма Краскала в C ++

Ниже приведен код для реализации в C ++. Мы используем стандартные библиотеки шаблонов, чтобы сделать нашу работу проще и чище.

Когда мы запускаем программу, мы получаем вывод как:

Алгоритм Краскала vs Прима

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

Рекомендуем хостинг TIMEWEB

Рекомендуемые статьи по этой тематике

По статье задано0 вопрос(ов)

Источник: Programiz

Подписчики

Платёжная система
  • mafulechka
  • 4917
  • 1
  • 3
  • 0

  • Vladimir Sergeevich
  • #
  • 25 июля 2019 г. 16:20
  • (ред.)

Я так понимаю, это перевод статьи?

Вот такие фразы выглядят стремно: «Любой минимальный алгоритм остовного дерева»
«популярным алгоритмом минимального остовного дерева»
Возможно, должно быть «алгоритмом построения . «

Первое предложение тоже несогласованное.

Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав print до вызова kruskal.

Не очевидна связь приведенного кода с описанным алгоритмом. — Что это за массив parent и почему (кстати) он не уничтожается в деструкторе?

Псевдокод не понятный. Что делает функция UNION(u, v) ?
Обе строки 7 и 8 вложены внутрь блока if?

У нормальной реализации алгоритма сложность N*log(N). А у вас для каждого узла графа вызывается функция find_set, которая имеет трудоемкость O(N). И того — O(N^2). Функция find_set при этом вообще особо кривая. Не понятно что она должна вернуть в каком случае.

Ну и еще, вот эта структура выглядит очень плохо:
vector

Алгоритмы на графах и деревьях

Сравнение алгоритмов КомпСвяз-Рек и КомпСвяз-Итер

В худшем случае (при полном графе ) рекурсивный алгоритм, перебирая все возможные ребра, будет вынужден вызвать основную процедуру (N-1) ! раз. Велика вероятность, что при достаточно большом N произойдет переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной матрицы смежности дают сильное ограничение на возможное количество вершин графа : не более 250 (см. лекцию 3).

Итеративный же алгоритм переберет все ребра графа, которых может быть не более чем N*(N+1)/2 . В половине этих случаев возможна ситуация объединения двух компонент связности в одну, для чего потребуется еще N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N 3 /8 . Возможное количество вершин графа ограничено только максимальным размером линейного массива ( 32 000 ).

Нахождение минимального каркаса

Задача. В заданном взвешенном связном графе определить множество ребер, составляющих некоторый его оптимальный каркас (например, минимальный по сумме весов входящих в него ребер).

Рекурсивный алгоритм

Алгоритм Каркас-Рек

Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-1 ребро 6 См. предыдущую лекцию. ( N — количество вершин графа ).

Реализация

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

Итеративный алгоритм

Алгоритм Краскала
  1. Упорядочить все ребра графа по возрастанию их весов.
  2. Применить алгоритм КомпСвяз-Итер (см. пункт «Подсчет количества компонент связности «).

Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено ( N-1 )-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).

Реализация

Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз-Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчет добавленных в каркас ребер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счетчик добавленных ребер станет равным N-1 .

Нахождение кратчайших путей

Задача. В заданном взвешенном связном графе найти расстояние (длину кратчайшего пути ) от выделенной вершины s до вершины t . Веса всех ребер строго положительны.

Рекурсивный алгоритм

Алгоритм Расст-Рек

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

Реализация

Пусть граф задан матрицей смежности sm , а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути «на возврате» совершается рекурсией автоматически, поскольку в ее заголовке использован параметр-значение , а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром-значением чересчур накладно:

Итеративный алгоритм

Алгоритм , предложенный Дейкстрой 7 Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959. , настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t , но и до всех остальных вершин графа .

Итак, пусть граф задан матрицей смежности .

Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt , символизирующими «бесконечность». По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.

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

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

Алгоритм Дейкстры

Расстояние от s до s , конечно же, равно 0 . Кроме того, это расстояние уже никогда не сможет стать меньше — ведь веса всех ребер графа у нас положительны. Таким образом:

Повторить N-1 раз следующие действия:

для всех непомеченных вершин х , связанных ребром с вершиной last , необходимо пересчитать расстояние:

Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел min , использованную в тексте программы, читатели смогут написать самостоятельно.

Сравнение алгоритмов Расст-Рек и Дейкстры

Сложность рекурсивного алгоритма пропорциональна N !, а алгоритм Дейкстры имеет сложность

Алгоритм Краскала

Алгоритм Йена

Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами. (Алгоритм Йена)

Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе соединяющих вершины u1, u2. Ищутся пути, которые не содержат петель. Алгоритм прислал

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

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

1. Найти минимальный путь P1=(v11. v1L[1]) .Положить k = 2. Включить P1 в результирующий список.

2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (kv1)-го кратчайшего пути Pk-1 для всех i=1,2. L[k-1], выполняя для каждого i

шаги с 3-го по 6-й.

3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2. kv1. Если да, положить W[vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).

4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11. vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам, входящим в корень.

5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его.

6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.

7. Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайших путей без петель.

Построения минимального остовного дерева (Алгоритм Краскала)

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

Вначале опишем алгоритм (возможно не достаточно строго), а затем обсудим, какой способ задания графа был бы наилучшим в данном случае, а так же покажем как от тех способов задания, которые мы использовали ранее перейти к способу применимому здесь.

Итак, алгоритм Краскала:

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

2. Полагаем, что каждая вершина относится к своей компоненте связности.

3. Проходим ребра в «отсортированном» порядке. Для каждого ребра выполняем:

Если вершины, соединяемые данным ребром, лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву.

Если вершины, соединяемые данным ребром, лежат в одной компоненте связности, то исключаем ребро из рассмотрения.

4. Если есть еще нерассмотренные ребра и не все компоненты связности

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

языков, то будем работать с простыми массивами. Для задания набора ребер используем два массива E: array [1..m,1..2] of integer — здесь m — количество ребер

Алгоритм Краскала – построение оптимального каркаса

В начале 19 века геометр из Берлина Якоб Штейнер поставил задачу, как соединить три деревни так, чтобы их протяженность была самой короткой. Впоследствии он обобщил эту задачу: требуется найти на плоскости такую точку, чтобы расстояние от нее до n других точек было наименьшим. В 20 веке продолжилась работа над этой темой. Было решено взять несколько точек и соединить их таким образом, чтобы расстояние между ними было самым коротким. Это все является частным случаем изучаемой проблемы.

«Жадные» алгоритмы

Алгоритм Краскала относится к «жадным» алгоритмам (их еще называют градиентными). Суть таковых – самый большой выигрыш на каждом шаге. Не всегда «жадные» алгоритмы дают наилучшее решение поставленной задачи. Существует теория, показывающая, что при их применении к определенным задачам они дают оптимальное решение. Это теория матроидов. Алгоритм Краскала относится к таким задачам.

Нахождение каркаса минимального веса

Рассматриваемый алгоритм строит оптимальный каркас графа. Задача о нем состоит в следующем. Дан неориентированный граф без кратных ребер и петель, и на множестве его ребер задана весовая функция w, которая приписывает каждому ребру e число – вес ребра – w(e). Вес каждого подмножества из множества ребер определяется суммой весов его ребер. Требуется найти каркас самого малого веса.

Описание

Алгоритм Краскала работает так. Сначала все ребра исходного графа располагаются в порядке возрастания весов. Первоначально каркас не содержит ни одного ребра, но включает все вершины графа. После очередного шага алгоритма к уже построенной части каркаса, которая является остовным лесом, добавляется одно ребро. Оно выбирается не произвольно. Все ребра графа, не принадлежащие каркасу, можно назвать красными и зелеными. Вершины каждого красного ребра находятся в одной компоненте связности строящегося леса, а вершины зеленого – в разных. Поэтому если добавить туда красное ребро, появляется цикл, а если зеленое – в полученном после этого шага лесе компонент связности будет меньше на одну. Таким образом, к полученному построению нельзя добавить ни одно красное ребро, но любое зеленое ребро прибавить можно, чтобы получить лес. И добавляется зеленое ребро с минимальным весом. В итоге получается каркас наименьшего веса.

Реализация

Обозначим текущий лес F. Он разбивает множество вершин графа на области связности (их объединение образует F, и они попарно не пересекаются). У красных ребер обе вершины лежат в одной части. Part(x) – функция, которая для каждой вершины x возвращает имя части, к которой принадлежит x. Unite(x,y) – это процедура, строящая новое разбиение, состоящее из объединения частей x и y и всех остальных частей. Пусть n – число ребер графа. Все эти понятия включены в алгоритм Краскала. Реализация:

Упорядочить все ребра графа от 1-го до n-го по возрастанию весов. (ai, bi – вершины ребра с номером i).

for i = 1 to n do.

If x не равно y then Unite (x, y), включить в F ребро с номером i.

Корректность

Пусть T – каркас исходного графа, построенный с помощью алгоритма Краскала, а S – его произвольный каркас. Нужно доказать, что w(T) не превосходит w(S).

Пусть M – множество ребер S, P – множество ребер T. Если S не равно T, то найдется ребро et каркаса T, не принадлежащее S. Присоединим et к S. Образуется цикл, назовем его C. Удалим из C любое ребро es, принадлежащее S. Получится новый каркас, потому что и ребер, и вершин в нем столько же. Его вес не превосходит w(S), так как w(et) не больше w(es) в силу алгоритма Краскала. Эту операцию (замену ребер S на ребра T) будем повторять до тех пор, пока не получим Т. Вес каждого последующего полученного каркаса не больше веса предыдущего, откуда следует, что w(T) не больше, чем w(S).

Также корректность алгоритма Краскала следует из теоремы Радо-Эдмондса о матроидах.

Примеры применения алгоритма Краскала

Дан граф с вершинами a, b, c, d, e и ребрами (a, b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Веса ребер показаны в таблице и на рисунке. Вначале строящийся лес F содержит все вершины графа и не содержит ни одного ребра. Алгоритм Краскала сначала добавит ребро (a, e), так как вес у него наименьший, и вершины a и e находятся в разных компонентах связности леса F (ребро (a, e) является зеленым), затем ребро (c, d), потому что у этого ребра наименьший вес из ребер графа, не принадлежащим F, и оно является зеленым, затем по тем же причинам добавляется ребро (a, b). А вот ребро (b, e) пропускается, хоть у него и наименьший вес из оставшихся ребер, потому что оно красное: вершины b и e принадлежат одной компоненте связности леса F, то есть если добавить к F ребро (b, e), образуется цикл. Затем добавляется зеленое ребро (b, c), пропускается красное ребро (c, e), а потом d, e. Таким образом, последовательно добавляются ребра (a, e), (c, d), (a, b), (b, c). Из нихер и состоит оптимальный каркас исходного графа. Так работает в данном случае алгоритм Краскала. Пример это показал.

На рисунке показан граф, состоящий из двух компонент связности. Жирными линиями показаны ребра оптимального каркаса (зеленые), построенного с помощью алгоритма Краскала.

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

Последовательность добавленных ребер: (1,6); (0,3), (2,6) или (2,6), (0,3) – значения не имеет; (3,4); (0,1), (1,6) или (1,6), (0,1), также безразлично (5,6).

Алгоритм Краскала находит практическое применение, например, для оптимизации прокладок коммуникаций, дорог в новых микрорайонах населенных пунктах каждой страны, а также в других случаях.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×