java - DB和java的最短路径问题

Question

我有一个电影数据库(postgreSQL)。其中一张表包含 Actor 和电影标题。我必须在java中解决的作业如下:两个 Actor (A和B)在同一部电影中连接在一起。另外两个 Actor ，A 和 B，当有第三个 Actor C 时也有联系，C 与他们一起在不同的电影中扮演(A 和 B 不一起扮演!)等等......我希望你明白想法:)现在我必须找到两个 Actor 之间的最短连接(=路径)。

现在开始实现:从数据库中获取数据(准备好的语句)并将名称(作为字符串)保存在链接列表中正在工作。以及 Actor 之间的简单联系，如 A -> B(= 都在同一部电影中扮演)。我在试图包含更复杂的连接(如 A -> B -> C)时遇到了困难。

我将 Actor 姓名存储在 HashMap 中，如下所示:

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

因此，当我加载第一个 Actor (约翰尼·德普)时，我将他的名字作为键，并在键引用的列表中与他一起玩的其他 Actor 。检查是否有其他 Actor 和他一起玩很容易:

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

但是...如果我正在寻找的 Actor 不在 HashMap 中(即当我必须更深一层才能找到他时)，我该怎么办？我假设我必须从connectedActors列表中选择第一个 Actor 的名字，将其作为新键插入到HashMap中，并获取与他一起玩的所有 Actor 并将其插入其中。然后在这个列表中搜索。
但这正是我无法弄清楚的部分。我已经尝试将名称存储在图形节点中并使用 bfs 来搜索它们，但这里也有同样的问题，只是不知道如何在不创建无限循环的情况下“向下一级”...有谁知道如何我能解决这个问题吗？我刚刚开始使用 java 以及一般的编程，所以它可能很简单，但我只是看不到它:/

Answer 1

首先，我会使用 Set 来存储与某人一起玩的 Actor :

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

而不是List以避免重复名称。

为了找出两个 Actor 之间的分离程度我将从一个 Actor 开始，生成由 分隔的所有 Actor 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;
}

我并不声称它是最有效的算法。上面的代码中也可能存在错误。