|
120
Глава 4.
Графовые задачи
Лос-
Анджелес
Хьюстон
Нью-Йорк
Майами
Чикаго
Даллас
Вашингтон
Филадельфия
Атланта
Бостон
Сан-Франциско
Феникс
Детройт
Сиэтл
613
190
81
123
482
396
238
543
923
588
604
968
702
721
225
805
1704
1737
887
1015
307
357
50
386
348
678
Риверсайд
Рис. 4.5.
Взвешенный граф с 15 самыми большими MSA Соединенных Штатов,
вес каждого ребра представляет собой расстояние между двумя MSA в милях
Алгоритму.Ярника,.о.котором.мы.вскоре.расскажем,.требуется.возможность.
сравнивать.ребра.между.собой,.чтобы.выбрать.из.них.ребро.с.меньшим.весом..
Это.легко.реализовать.посредством.числовых.весов.(листинг.4.7).
Листинг 4.7.
WeightedEdge.java
package
chapter4;
public class
WeightedEdge
extends
Edge
implements
Comparable {
public final double
weight;
public
WeightedEdge(
int
u,
int
v,
double
weight) {
super
(u, v);
this
.weight = weight;
}
@Override
public
WeightedEdge reversed() {
return new
WeightedEdge(v, u, weight);
}
// так можно упорядочить ребра по весу и найти ребро с минимальным весом
@Override
public int
compareTo(WeightedEdge other) {
Double mine = weight;
Double theirs = other.weight;
return
mine.compareTo(theirs);
4.4. Минимизация затрат на построение сети
121
}
@Override
public
String toString() {
return
u + " " + weight + "> " + v;
}
}
Реализация.
WeightedEdge
.не.сильно.отличается.от.
Edge
..Разница.только.в.том,.
что.добавлено.свойство.
weight
.и.реализован.интерфейс.
Comparable
.с.помощью.
compareTo()
,.благодаря.чему.два.объекта.
WeightedEdge
.можно.сравнивать..
Метод.
compareTo()
.просматривает.только.веса.ребер.(а.не.унаследованные.
свойства.
u
.и.
v
),.так.как.алгоритм.Ярника.осуществляет.поиск.наименьшего.
по.весу.ребра.
Класс.
WeightedGraph
.наследует.б
ольшую.часть.своей.функциональности.от.
Graph
..
Помимо.этого,.у.данного.класса.есть.методы.инициализации.и.удобные.методы.
сложения.объектов.
WeightedEdge
..К.тому.же.в.нем.реализована.собственная.версия.
toString()
.(листинг.4.8).
Листинг 4.8.
WeightedGraph.java
package
chapter4;
import
java.util.Arrays;
import
java.util.Collections;
import
java.util.HashMap;
import
java.util.LinkedList;
import
java.util.List;
import
java.util.Map;
import
java.util.PriorityQueue;
import
java.util.function.IntConsumer;
public class
WeightedGraph
extends
Graph {
public
WeightedGraph(List vertices) {
super
(vertices);
}
// Это невзвешенный граф, поэтому мы всегда
// добавляем ребра в обоих направлениях
public void
addEdge(WeightedEdge edge) {
edges.get(edge.u).add(edge);
edges.get(edge.v).add(edge.reversed());
}
public void
addEdge(
int
u,
int
v,
float
weight) {
addEdge(
new
WeightedEdge(u, v, weight));
}
public void
addEdge(V first, V second,
float
weight) {
122
Глава 4.
Графовые задачи
addEdge(indexOf(first), indexOf(second), weight);
}
// упрощенная печать графика
@Override
public
String toString() {
StringBuilder sb =
new
StringBuilder();
for
(
int
i = 0; i < getVertexCount(); i++) {
sb.append(vertexAt(i));
sb.append(" -> ");
sb.append(Arrays.
toString
(edgesOf(i).stream()
.map(we -> "(" + vertexAt(we.v) + ", " + we.weight +
")").toArray()));
sb.append(System.
lineSeparator
());
}
return
sb.toString();
}
Теперь.можно.наконец.определить.взвешенный.граф..Взвешенный.граф,.с.которым.
мы.будем.работать.(см..рис..4.5),.называется.
cityGraph2
.(листинг.4.9).
Листинг 4.9.
WeightedGraph.java (продолжение)
public static void
main(String[] args) {
// представляет 15 крупнейших MSA в США.
WeightedGraph cityGraph2 =
new
WeightedGraph<>(
List.
of
("Seattle", "San Francisco", "Los Angeles", "Riverside",
"Phoenix", "Chicago", "Boston", "New York", "Atlanta", "Miami",
"Dallas", "Houston", "Detroit", "Philadelphia", "Washington"));
cityGraph2.addEdge("Seattle", "Chicago", 1737);
cityGraph2.addEdge("Seattle", "San Francisco", 678);
cityGraph2.addEdge("San Francisco", "Riverside", 386);
cityGraph2.addEdge("San Francisco", "Los Angeles", 348);
cityGraph2.addEdge("Los Angeles", "Riverside", 50);
cityGraph2.addEdge("Los Angeles", "Phoenix", 357);
cityGraph2.addEdge("Riverside", "Phoenix", 307);
cityGraph2.addEdge("Riverside", "Chicago", 1704);
cityGraph2.addEdge("Phoenix", "Dallas", 887);
cityGraph2.addEdge("Phoenix", "Houston", 1015);
cityGraph2.addEdge("Dallas", "Chicago", 805);
cityGraph2.addEdge("Dallas", "Atlanta", 721);
cityGraph2.addEdge("Dallas", "Houston", 225);
cityGraph2.addEdge("Houston", "Atlanta", 702);
cityGraph2.addEdge("Houston", "Miami", 968);
cityGraph2.addEdge("Atlanta", "Chicago", 588);
cityGraph2.addEdge("Atlanta", "Washington", 543);
cityGraph2.addEdge("Atlanta", "Miami", 604);
cityGraph2.addEdge("Miami", "Washington", 923);
cityGraph2.addEdge("Chicago", "Detroit", 238);
cityGraph2.addEdge("Detroit", "Boston", 613);
cityGraph2.addEdge("Detroit", "Washington", 396);
4.4. Минимизация затрат на построение сети
123
cityGraph2.addEdge("Detroit", "New York", 482);
cityGraph2.addEdge("Boston", "New York", 190);
cityGraph2.addEdge("New York", "Philadelphia", 81);
cityGraph2.addEdge("Philadelphia", "Washington", 123);
System.
out
.println(cityGraph2);
}
}
Поскольку.в.
WeightedGraph
.реализован.метод.
toString()
,.мы.можем.структурно.
распечатать.
cityGraph2
..При.выводе.вы.увидите.и.вершины,.с.которыми.соединена.
данная.вершина,.и.веса.этих.соединений:
Seattle -> [(Chicago, 1737.0), (San Francisco, 678.0)]
San Francisco -> [(Seattle, 678.0), (Riverside, 386.0), (Los Angeles, 348.0)]
Los Angeles -> [(San Francisco, 348.0), (Riverside, 50.0), (Phoenix, 357.0)]
Riverside -> [(San Francisco, 386.0), (Los Angeles, 50.0), (Phoenix, 307.0),
(Chicago, 1704.0)]
Phoenix -> [(Los Angeles, 357.0), (Riverside, 307.0), (Dallas, 887.0), (Houston,
1015.0)]
Chicago -> [(Seattle, 1737.0), (Riverside, 1704.0), (Dallas, 805.0), (Atlanta,
588.0), (Detroit, 238.0)]
Boston -> [(Detroit, 613.0), (New York, 190.0)]
New York -> [(Detroit, 482.0), (Boston, 190.0), (Philadelphia, 81.0)]
Atlanta -> [(Dallas, 721.0), (Houston, 702.0), (Chicago, 588.0), (Washington,
543.0), (Miami, 604.0)]
Miami -> [(Houston, 968.0), (Atlanta, 604.0), (Washington, 923.0)]
Dallas -> [(Phoenix, 887.0), (Chicago, 805.0), (Atlanta, 721.0), (Houston,
225.0)]
Houston -> [(Phoenix, 1015.0), (Dallas, 225.0), (Atlanta, 702.0), (Miami, 968.0)]
Detroit -> [(Chicago, 238.0), (Boston, 613.0), (Washington, 396.0), (New York,
482.0)]
Philadelphia -> [(New York, 81.0), (Washington, 123.0)]
Washington -> [(Atlanta, 543.0), (Miami, 923.0), (Detroit, 396.0), (Philadelphia,
123.0)]
Do'stlaringiz bilan baham: |
