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

118
Глава 4.
Графовые задачи
К.счастью,.у.нас.уже.есть.алгоритм.поиска.кратчайших.путей,.и.с.его.помощью.мы.
можем.ответить.на.этот.вопрос..Поиск.в.ширину,.описанный.в.главе.2,.подходит.
для.графов.так.же,.как.и.для.лабиринтов..В.сущности,.лабиринты,.с.которыми.
мы.работали.в.главе.2,.на.самом.деле.являются.графами..Вершины.—.это.точки.
лабиринта,.а.ребра.—.ходы,.которые.можно.сделать,.чтобы.попасть.из.одной.точки.
в.другую..В.невзвешенном.графе.поиск.в.ширину.найдет.кратчайший.путь.между.
любыми.двумя.вершинами.
Мы.можем.повторно.использовать.реализацию.поиска.в.ширину,.представлен-
ную.в.главе.2,.для.работы.с.
Graph
..Да.что.там,.ее.можно.применить.вообще.без.
изменений..Вот.что.значит.параметризованный.код!
Напомню,.что.функции.
bfs()
,.описанной.в.главе.2,.требуются.три.параметра:.на-
чальное.состояние,.
Predicate
.(объект,.похожий.на.функцию.чтения,.возвращающую.
значение.
boolean
).для.проверки.того,.достигнута.ли.цель,.и.
Function
.для.поиска.со-
стояний.—.наследников.данного.состояния..Начальным.состоянием.будет.вершина,.
представленная.строкой.
"Boston"
,.целевым.тестом.—.лямбда-функция,.которая.про-
веряет,.является.ли.данная.вершина.вершиной.
"Miami"
..Наконец,.вершины-наслед-
ники.могут.быть.сгенерированы.с.помощью.метода.
neighborsOf()
.из.класса.
Graph
.
Учитывая.этот.план,.мы.можем.добавить.соответствующий.код.в.конец.основного.
раздела.
main()
.файла.
UnweightedGraph.java
,.чтобы.найти.на.
cityGraph
.кратчайший.
маршрут.между.Бостоном.и.Майами.(листинг.4.6).
ПРИМЕЧАНИЕ
В.листинг.4.4.(ранее.в.главе,.где.впервые.был.определен.UnweightedGraph).включены.
операции. импорта. (например,. chapter2.GenericSearch,. chapter2.genericSearch.Node)..
Это.работает,.только.если.пакет.chapter2.доступен.из.пакета.chapter4..Если.среда.раз-
работки. не. настроена. таким. образом,. вы. сможете. скопировать. класс. GenericSearch.
непосредственно.в.пакет.chapter4.и.исключить.импорт.
Листинг 4.6. 
UnweightedGraph.java (продолжение)
Node bfsResult = GenericSearch.
bfs
("Boston",
v -> v.equals("Miami"),
cityGraph::neighborsOf);