Проблема кратчайшего пути с БД и Java

Question

У меня есть база данных фильмов (postgreSQL).Одна из таблиц содержит актеров и названия фильмов.Задание, которое я должен решить в Java, заключается в следующем: два актера (A и B) связаны друг с другом, когда они в одном фильме.Кроме того, два актера, A и B, также связаны, когда есть третий актер C, который играет с ними обоими в разных фильмах (A и B не играют вместе!) И так далее ... Я надеюсь, что вы получитеидея :) Теперь мне нужно найти кратчайшее соединение (= путь) между двумя действующими лицами.

Теперь к реализации: выборка данных из БД (подготовленные операторы) и сохранение имен (в виде строк) всвязанный список работает.А также простая связь между актерами, такими как A -> B (= оба играют в одном фильме).Я бью стену, пытаясь включить более сложные соединения (например, A -> B -> C).

Я храню имена актеров в HashMap, например:

Map<String, List<String>> actorHashMap = new HashMap<String, List<String>>();

Поэтому, когда я загружаю первого актера (Джонни Деппа), в качестве ключа я использую его имя, а другие актеры играют с ним в списке, на который ссылается ключ.Легко проверить, играл ли с ним другой актер:

List<String> connectedActors = actorHashMap.get(sourceActor);
if(connectedActors.contains(actor)) {
         found = true; }

Но ... что мне делать, если искомого актера нет в HashMap (т. Е. Когда мне нужно идти одинуровень глубже его найти)?Я предполагаю, что мне нужно будет выбрать имя первого актера из списка подключенных актеров, вставить его как новый ключ в HashMap и выбрать всех актеров, с которыми он играл вместе с ним, чтобы вставить их.Затем поищите в этом списке.
Но это именно та часть, которую я не могу понять.Я уже пытался хранить имена в графических узлах и использовать bfs для их поиска, но та же проблема здесь, просто не знаю, как перейти на «один уровень вниз» без создания бесконечного цикла ... У кого-нибудь есть идеи, какя могу решить это?Я только начинаю с Java, а также программирую в целом, так что это, вероятно, просто, но я просто не вижу этого: /

Answer 1

Сначала я бы использовал Set для хранения актеров, с которыми играл кто-то:

Map<String, Set<String>> actorHashMap = ...

вместо List, чтобы избежать дублирования имен.

Чтобы узнать, сколько степеней разделения между двумя актерами Я бы начал с одного актера и сгенерировал бы всех актеров, которые разделены 1, 2, 3 ... градусов. Я бы установил максимальную глубину поиска, однако в этом нет необходимости, если число актеров не слишком велико.

String actor = "Johnny Depp";
String targetActor = "John Travolta";
Map<String, Integer> connectedActorsAndDepth = new HashMap<String, Integer>();
Integer depth = 1;
Set<String> actorsAddedAtCurrentDepth = actorHashMap.get(actor);
for (String otherActor : actorsAddedAtPrecedingDepth) {
    if (otherActor.equals(targetActor)) return depth;
    connectedActorsAndDepth.put(otherActor, depth);
}
Set<String> actorsAddedAtPrecedingDepth = actorAddedAtCurrentDepth;
Integer maxDepth = 10;
while (++depth < maxDepth) {
    actorsAddedAtCurrentDepth = new HashSet<String>():
    for (String otherActor : actorsAddedAtPrecedingDepth) {
       if (otherActor.equals(targetActor)) return depth;
       if (!connectedActorsAndDepth.contains(otherActor)) {
           actorsAddedAtCurrentDepth.add(otherActor);
           connectedActorsAndDepth.put(otherActor, depth);
       }
    }
    actorsAddedAtPrecedingDepth = actorsAddedAtCurrentDepth;
}

Я не утверждаю, что это самый эффективный алгоритм. Также могут быть ошибки в коде выше.