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

4.2.1. Работа с Edge и UnweightedGraph
Теперь,.когда.у.нас.есть.конкретные.реализации.
Edge
.и.
Graph
,.можем.создать.
представление.потенциальной.сети.Hyperloop..Вершины.и.ребра.в.
cityGraph
.
соответствуют.вершинам.и.ребрам,.представленным.на.рис..4.2..Используя.
параметризацию,.мы.можем.указать,.что.вершины.будут.иметь.тип.
String
(UnweightedGraph)
..Другими.словами,.тип.
String
.заменяет.переменную.
типа.
V
.(листинг.4.5).

---

116
Глава 4.
Графовые задачи
Листинг 4.5. 
UnweightedGraph.java (продолжение)
public static void 
main(String[] args) {
// Представляет 15 крупнейших MSA в США.
UnweightedGraph cityGraph = 
new 
UnweightedGraph<>(
List.
of
("Seattle", "San Francisco", "Los Angeles", "Riverside", 
"Phoenix", "Chicago", "Boston", "New York", "Atlanta", 
"Miami", "Dallas", "Houston", "Detroit", "Philadelphia", 
"Washington"));
cityGraph.addEdge("Seattle", "Chicago");
cityGraph.addEdge("Seattle", "San Francisco");
cityGraph.addEdge("San Francisco", "Riverside");
cityGraph.addEdge("San Francisco", "Los Angeles");
cityGraph.addEdge("Los Angeles", "Riverside");
cityGraph.addEdge("Los Angeles", "Phoenix");
cityGraph.addEdge("Riverside", "Phoenix");
cityGraph.addEdge("Riverside", "Chicago");
cityGraph.addEdge("Phoenix", "Dallas");
cityGraph.addEdge("Phoenix", "Houston");
cityGraph.addEdge("Dallas", "Chicago");
cityGraph.addEdge("Dallas", "Atlanta");
cityGraph.addEdge("Dallas", "Houston");
cityGraph.addEdge("Houston", "Atlanta");
cityGraph.addEdge("Houston", "Miami");
cityGraph.addEdge("Atlanta", "Chicago");
cityGraph.addEdge("Atlanta", "Washington");
cityGraph.addEdge("Atlanta", "Miami");
cityGraph.addEdge("Miami", "Washington");
cityGraph.addEdge("Chicago", "Detroit");
cityGraph.addEdge("Detroit", "Boston");
cityGraph.addEdge("Detroit", "Washington");
cityGraph.addEdge("Detroit", "New York");
cityGraph.addEdge("Boston", "New York");
cityGraph.addEdge("New York", "Philadelphia");
cityGraph.addEdge("Philadelphia", "Washington");
System.
out
.println(cityGraph.toString());
}
}
У.
cityGraph
.есть.вершины.типа.
String
.—.мы.указываем.для.каждой.название.
MSA,.который.она.представляет..Последовательность,.в.которой.добавляем.
ребра.в.
cityGraph
,.не.имеет.значения..Поскольку.мы.реализовали.
toString()
.
с.красиво.напечатанным.описанием.графа,.теперь.можно.структурно.распечатать.
(это.настоящий.термин!).граф..У.вас.должен.получиться.результат,.подобный.
следующему:
Seattle -> [Chicago, San Francisco]
San Francisco -> [Seattle, Riverside, Los Angeles]
Los Angeles -> [San Francisco, Riverside, Phoenix]
Riverside -> [San Francisco, Los Angeles, Phoenix, Chicago]
Phoenix -> [Los Angeles, Riverside, Dallas, Houston]
Chicago -> [Seattle, Riverside, Dallas, Atlanta, Detroit]

---

4.3. Поиск кратчайшего пути
117
Boston -> [Detroit, New York]
New York -> [Detroit, Boston, Philadelphia]
Atlanta -> [Dallas, Houston, Chicago, Washington, Miami]
Miami -> [Houston, Atlanta, Washington]
Dallas -> [Phoenix, Chicago, Atlanta, Houston]
Houston -> [Phoenix, Dallas, Atlanta, Miami]
Detroit -> [Chicago, Boston, Washington, New York]
Philadelphia -> [New York, Washington]
Washington -> [Atlanta, Miami, Detroit, Philadelphia]