Используйте BFS для поиска по графику, который представляет проблему цепочки слов в Java

Question

Мне нужно использовать поиск в ширину для проблемы цепочки слов. У меня есть текстовый файл с 5-буквенными словами, цель состоит в том, чтобы использовать эти слова и создать график, который показывает связь между словами на основе первых слов и 4 последних букв, если их можно найти в следующем слове. Например, подняться → дирижабль → лимпс → писмо → влажный. Таким образом, c limb переходит к blim p, потому что у них обоих есть l, i, m и b, , но дирижабль не может вернуться, чтобы подняться, потому что четыре последних буквы о подъеме не в дирижабле.

Я не совсем уверен, как решить эту проблему и показать графическое представление, чтобы я мог использовать BFS на нем.

Я пытался реализовать граф в Eclipse с помощью Java с использованием алгоритмов Седжвикса, 4-е издание, однако это довольно расплывчато, поскольку в этом примере, кажется, отсутствуют шаги. Я новичок, поэтому я был бы признателен за базовые шаги или пример кода с объяснением, основанным на алгоритмах Седжвикса о том, как решить эту проблему, поскольку я пытался решить его сам, но безуспешно.

Я хотел бы, чтобы программа показывала ориентированный граф со словами и ребрами между словами (вершина), а также была в состоянии использовать BFS.

Answer 1

Во-первых, ради производительности вы строите Map<String, List<String>> нормализованных 4-буквенных комбинаций в список слов с этими 4 буквами.

например. climb имеет 5 различных комбинаций из 4 букв, которые могут привести к слову: limb, cimb, clmb, clib и clim. Поскольку порядок букв не имеет значения, вы нормализуете его, сортируя буквы: bilm, bcim, bclm, bcil и cilm.

Каждое слово является узлом в вашем графе, и пять нормализованных 4-буквенных комбинаций являются доступными "портами" для ребер из других слов. Имея карту на месте, вы можете очень быстро найти все узлы слов, по которым вы можете перемещаться, от заданного узла, взяв последние 4 буквы, нормализовав их и посмотрев на карту (конечно, за исключением самого узла).

например. со словами climb, blimp и limps вы получите следующую карту:

bcil -> climb
bcim -> climb
bclm -> climb
bilm -> climb, blimp
bilp -> blimp
bimp -> blimp
blmp -> blimp
cilm -> climb
ilmp -> blimp, limps
ilms -> limps
ilps -> limps
imps -> limps
lmps -> limps

Конечно, любая запись на карте, содержащая только одно слово в списке, является словом, указывающим на себя, поэтому они неактуальны и могут быть удалены. Хотя в коде нет особой причины делать это на самом деле, для удобства людей полезными являются следующие элементы карты:

bilm -> climb, blimp
ilmp -> blimp, limps

Теперь вы можете строить свои края:

climb --[bilm]-> blimp
blimp --[ilmp]-> limps
limps --[imps]-> 

Здесь не происходит BFS.
Построение карты: O (n) .
Создание узлов: O (n) .
Создание ребер: O (n * m) , где m - среднее количество ребер на узел. Поскольку m, вероятно, приближается к константе для больших графов, ее можно исключить.
Это означает, что общее решение составляет O (n) .