Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Вычисление общего веса взвешенного пути
Прежде.чем.разработать.метод.поиска.минимального.связующего.дерева,.соз-
дадим.функцию,.которую.сможем.использовать.для.проверки.суммарного.веса.
решения..Найденное.минимальное.связующее.дерево.будет.представлять.собой.
список.взвешенных.ребер,.из.которых.оно.состоит..Сначала.мы.определим.взве-
шенный.путь.как.список.
WeightedEdge
..Затем.определим.функцию.
totalWeight()
,.
которая.принимает.список.
WeightedEdges
.и.находит.общий.вес,.получаемый.
в.результате.сложения.всех.весов.ее.ребер..Обратите.внимание.на.то,.что.этот.
метод.и.остальные.в.данной.главе.будут.добавлены.к.существующему.классу.
WeightedGraph
.(листинг.4.10).
Листинг 4.10. 
WeightedGraph.java (продолжение)
public static double 
totalWeight(List path) {
return 
path.stream().mapToDouble(we -> we.weight).sum();
}

---

4.4. Минимизация затрат на построение сети
125
Алгоритм Ярника
Алгоритм.Ярника.для.поиска.минимального.связующего.дерева.решает.задачу.
посредством.деления.графа.на.две.части:.вершины.в.формируемом.минимальном.
связующем.дереве.и.вершины,.еще.не.входящие.в.минимальное.связующее.дерево..
Алгоритм.состоит.из.следующих.шагов.
1.. Выбрать.произвольную.вершину.для.включения.в.минимальное.связующее.
дерево.
2.. Найти.ребро.с.наименьшим.весом,.соединяющее.минимальное.связующее.
дерево.с.вершинами,.еще.не.входящими.в.минимальное.связующее.дерево.
3.. Добавить.вершину,.расположенную.на.конце.этого.минимального.ребра,.к.ми-
нимальному.связующему.дереву.
4.. Повторять.шаги.2.и.3,.пока.все.вершины.графа.не.будут.включены.в.мини-
мальное.связующее.дерево.
ПРИМЕЧАНИЕ
Алгоритм.Ярника.часто.называют.алгоритмом.Прима..Два.чешских.математика,.Ота-
кар.Борувка.и.Войцех.Ярник,.заинтересовавшись.минимизацией.затрат.на.прокладку.
электрических.линий.в.конце.1920-х.годов,.придумали.алгоритмы.для.решения.задачи.
поиска.минимального.связующего.дерева..Их.алгоритмы.были.«переоткрыты».другими.
учеными.несколько.десятков.лет.спустя
1
.
Для.эффективного.выполнения.алгоритма.Ярника.используется.очередь.с.приори-
тетом.(см..главу.2)..Каждый.раз,.когда.новая.вершина.добавляется.в.минимальное.
связующее.дерево,.все.ее.исходящие.ребра,.которые.связываются.с.вершинами.вне.
дерева,.добавляются.в.очередь.с.приоритетом..Ребро.с.наименьшим.весом.всегда.
первым.извлекается.из.очереди.с.приоритетом,.и.алгоритм.продолжает.выпол-
няться.до.тех.пор,.пока.очередь.с.приоритетом.не.опустеет..Это.гарантирует,.что.
ребра.с.наименьшим.весом.всегда.будут.первыми.добавляться.в.дерево..Ребра,.
которые.соединяются.с.вершинами,.уже.относящимися.к.дереву,.игнорируются.
при.извлечении.из.очереди.
Далее.представлен.код.функции.
mst()
.—.полная.реализация.алгоритма.Ярника,.
а.также.вспомогательная.функция.для.печати.взвешенного.пути.(листинг.4.11).
ПРЕДУПРЕЖДЕНИЕ
Алгоритм.Ярника.не.всегда.правильно.работает.для.графов.с.направленными.ребрами..
Он.не.подействует.и.для.несвязных.графов.
1
.
Durnov
á
 H.
.Otakar.Bor
ů
vka.(1899–1995).and.the.Minimum.Spanning.Tree..—.Institute.of.
Mathematics.of.the.Czech.Academy.of.Sciences,.2006..http://mng.bz/O2vj.

---