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

package 
chapter4;
import 
java.util.ArrayList;
import 
java.util.Arrays;
import 
java.util.List;
import 
java.util.stream.Collectors;
// V — тип вершин графа
// E — тип ребер
public abstract class 
Graphextends 
Edge> {
private 
ArrayList vertices = 
new 
ArrayList<>();
protected 
ArrayList> edges = 
new 
ArrayList<>();
public 
Graph() {
}
public 
Graph(List vertices) {
this
.vertices.addAll(vertices);
for 
(V vertex : vertices) {
edges.add(
new 
ArrayList<>());
}
}

---

112
Глава 4.
Графовые задачи
Список.
vertices
.—.это.сердце.графа..Все.вершины.сохраняются.в.списке,.а.впо-
следствии.мы.будем.ссылаться.на.них.по.их.целочисленному.индексу.в.нем..Сама.
вершина.может.быть.сложным.типом.данных,.но.ее.индекс.всегда.имеет.тип.
int
,.с.которым.легко.работать..На.другом.уровне,.между.графовыми.алгоритма-
ми.и.массивом.
vertices
,.этот.индекс.позволяет.получить.две.вершины.с.одним.
и.тем.же.именем.в.одном.графе.(представьте.себе.граф,.в.котором.вершинами.
являются.города.некоей.страны,.причем.среди.них.несколько.носят.название.
«Спрингфилд»)..Несмотря.на.одинаковое.имя,.они.будут.иметь.разные.цело-
численные.индексы.
Существует.множество.способов.реализации.структуры.данных.графа,.но.самые.
распространенные.—.использование.
матрицы вершин
.или.
списков смежности
..
В.матрице.вершин.каждая.ячейка.представляет.собой.пересечение.двух.вершин.
графа,.и.значение.этой.ячейки.указывает.на.связь.(или.ее.отсутствие).между.этими.
вершинами..В.нашей.структуре.данных.графа.задействуются.списки.смежности..
В.таком.представлении.у.каждой.вершины.есть.список.вершин,.с.которыми.она.
связана..В.нашем.конкретном.представлении.применяется.список.списков.ребер,.
поэтому.для.каждой.вершины.существует.список.ребер,.которыми.она.связана.
с.другими.вершинами..Этот.список.списков.называется.
edges
.
Далее.представлена.остальная.часть.класса.
Graph
.во.всей.своей.полноте.(ли-
стинг.4.3)..Обратите.внимание.на.применение.коротких,.в.основном.одностроч-
ных.методов.с.подробными.и.понятными.именами..Благодаря.этому.остальная.