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

while 
(!pq.isEmpty()) { // продолжаем, пока остаются необработанные вершины
WeightedEdge edge = pq.poll();
if 
(visited[edge.v]) {
continue
; // никогда не просматриваем дважды
}
// на данный момент это минимальный вес, так что добавляем в дерево
result.add(edge);

---

128
Глава 4.
Графовые задачи
visit.accept(edge.v); // посетите места соединений
}
return 
result; 
Пока.в.очереди.с.приоритетом.остаются.ребра,.мы.извлекаем.их.оттуда.и.про-
веряем,.ведут.ли.они.к.вершинам,.которых.еще.нет.в.дереве..Поскольку.очередь.
с.приоритетом.возрастающая,.из.нее.сначала.извлекаются.ребра.с.наименьшим.
весом..Это.гарантирует,.что.результат.действительно.имеет.минимальный.общий.
вес..Если.ребро,.извлеченное.из.очереди,.не.приводит.к.неисследованной.вершине,.
то.оно.игнорируется..В.противном.случае,.поскольку.ребро.имеет.минимальный.
из.всех.видимых.весов,.оно.добавляется.к.результирующему.набору.и.исследу-
ется.новая.вершина,.к.которой.ведет.это.ребро..Когда.неисследованных.ребер.не.
остается,.возвращается.результат.
Теперь.мы.наконец.вернемся.к.задаче.соединения.всех.15.крупнейших.MSA.Со-
единенных.Штатов.в.сеть.Hyperloop.минимальным.количеством.трасс..Марш-
рут,.выполняющий.эту.задачу,.—.это.просто.минимальное.связующее.дерево.
для.
cityGraph2
..Попробуем.запустить.
mst()
.для.
cityGraph2
.с.помощью.
main()
.
(листинг.4.12).
Листинг 4.12. 
WeightedGraph.java (продолжение)
List mst = cityGraph2.mst(0);
cityGraph2.printWeightedPath(mst);
Благодаря.методу.структурной.печати.
printWeightedPath()
.минимальное.свя-
зующее.дерево.легко.читается:
Seattle 678.0> San Francisco
San Francisco 348.0> Los Angeles
Los Angeles 50.0> Riverside
Riverside 307.0> Phoenix
Phoenix 887.0> Dallas
Dallas 225.0> Houston
Houston 702.0> Atlanta
Atlanta 543.0> Washington
Washington 123.0> Philadelphia
Philadelphia 81.0> New York
New York 190.0> Boston
Washington 396.0> Detroit
Detroit 238.0> Chicago
Atlanta 604.0> Miami
Total Weight: 5372.0
Другими.словами,.это.суммарно.кратчайший.набор.ребер,.который.соединяет.
все.MSA.во.взвешенном.графе..Минимальная.длина.трассы,.необходимой.для.
соединения.всех.ребер,.составляет.5372.мили..Минимальное.связующее.дерево.
показано.на.рис..4.7.

---

4.5. Поиск кратчайших путей во взвешенном графе