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

126
Глава 4.
Графовые задачи
Листинг 4.11. 
WeightedGraph.java (продолжение)
public 
List mst(
int 
start) {
LinkedList result = 
new 
LinkedList<>(); // здесь мы уже 
// были
if 
(start < 0 || start > (getVertexCount() — 1)) {
return 
result;
}
PriorityQueue pq = 
new 
PriorityQueue<>();
boolean
[] visited = 
new boolean
[getVertexCount()]; 
// это похоже на внутреннюю функцию "visit"
IntConsumer visit = index -> {
visited[index] = 
true
; // пометить как прочитанное
for 
(WeightedEdge edge
 
: edgesOf(index)) {
// добавляем все ребра отсюда в pq
if 
(!visited[edge.v]) {
pq.offer(edge);
}
}
};
visit.accept(start); // первая вершина, с которой все начинается
while 
(!pq.isEmpty()) { // продолжаем, пока остаются необработанные 
// вершины
WeightedEdge edge = pq.poll();
if 
(visited[edge.v]) {
continue
; // никогда не просматриваем дважды
}
// на данный момент это минимальный вес, так что добавляем в дерево
result.add(edge);
visit.accept(edge.v); // посетите места соединений
}
return 
result;
}
public void 
printWeightedPath(List wp) {
for 
(WeightedEdge edge : wp) {
System.
out
.println(vertexAt(edge.u) + " "
+ edge.weight + "> " + vertexAt(edge.v));
}
System.
out
.println("Total Weight: " + 
totalWeight
(wp));
}
Рассмотрим.функцию.
mst()
.построчно:
public 
List mst(
int 
start) {
LinkedList result = 
new 
LinkedList<>(); // здесь мы уже были
if 
(start < 0 || start > (getVertexCount() — 1)) {
return 
result;
}
Алгоритм.возвращает.взвешенный.путь.(
List
),.представляющий.
собой.минимальное.связующее.дерево..Если.значение.
start
.оказалось.неверным,.

---

4.4. Минимизация затрат на построение сети
127
то.
mst()
.возвращает.
None
..В.итоге.
result
.будет.содержать.взвешенный.путь,.куда.
входит.минимальное.связующее.дерево..Именно.здесь.добавляются.объекты.
WeightedEdges
,.так.как.ребро.с.наименьшим.весом.извлекается.из.очереди.и.пере-
водит.нас.к.новой.части.графа.
PriorityQueue pq = 
new 
PriorityQueue<>();
boolean
[] visited = 
new boolean
[getVertexCount()]; // здесь мы уже были
Алгоритм.Ярника.считается.
жадным
.
алгоритмом
,.потому.что.всегда.выбирает.
ребро.с.наименьшим.весом..В.
pq
.хранятся.новые.обнаруженные.ребра,.и.отсюда.
извлекается.следующее.ребро.с.наименьшим.весом..В.
visited
.отслеживаются.
индексы.вершин,.которые.мы.уже.просмотрели..Это.можно.сделать.также.с.по-
мощью.
Set
,.аналогичного.
explored
.в.
bfs()
:
IntConsumer visit = index -> {
visited[index] = 
true
; // пометить как прочитанное
for 
(WeightedEdge edge : edgesOf(index)) {
// добавляем все ребра отсюда в pq
if 
(!visited[edge.v]) {
pq.offer(edge);
}
}
}; 
visit()
.—.это.внутренняя.вспомогательная.функция,.которая.отмечает.вершину.
как.просмотренную.и.добавляет.в.
pq
.все.ее.ребра,.которые.соединяются.с.еще.
не.просмотренными.вершинами..Функция.
visit
.реализована.как.
IntConsumer
,.
представляющая.собой.просто.функцию,.которая.принимает.
int
.в.качестве.един-
ственного.параметра..В.этом.случае.
int
.будет.индексом.посещаемой.вершины..
Обратите.внимание.на.то,.как.легко.модель.списка.смежности.облегчает.поиск.
ребер,.принадлежащих.определенной.вершине:
visit.accept(start); // первая вершина, с которой все начинается
accept()
.—.это.метод.
IntConsumer
,.вызывающий.связанную.с.ним.функцию.
с.предоставленным.параметром.
int
..Неважно,.какая.вершина.будет.посещена.
первой,.если.граф.несвязный..Если.несвязный.граф.состоит.из.разъединенных.
компонентов,.то.
mst()
.вернет.дерево,.охватывающее.тот.
компонент
,.которому.
принадлежит.начальная.вершина: