JAVA

Question

我正在为一个简单的社交网络开发无向图实现。用户使用他们的 ID（整数）表示，我需要找到不同级别的友谊。
我使用了邻接列表方法，因为我的图非常稀疏。我使用哈希图来保存用户和他们的朋友：

Map<Integer, Set<Integer>> graph;

使用这个实现，我能够找到第一级和第二级友谊。但是，我写了一个方法，使用 BFS 来查找两个用户是否是四级朋友。

例如，如果图形包含以下边：
1-2
2-3
3-4
4-5
那么1和5就是四级好友了，我的方法在把1和5作为参数传给它的时候应该return为真。

问题是我的方法在主调用时总是returns false，即使方法本身经过测试是正确的！这是方法，它又是正确的并且有效。

public boolean checkLevelBFS(Integer source, Integer dest) {
    Queue<Integer> toVisitQueue = new LinkedList<>(graph.get(source));
    Set<Integer> visited = new HashSet<>();
    visited.add(source);
    Integer inreaser = new Integer(-1); // indicator for level increase
    toVisitQueue.add(inreaser);
    int level = 1; // because we already passed the source and started from its children nodes
    while (level <= 4 && !toVisitQueue.isEmpty()) {
        Integer currentNode = toVisitQueue.remove();
        if (currentNode.equals(dest)) {
            return true;
        }
        if (visited.contains(currentNode)) {
            continue;
        }
        if (currentNode.equals(inreaser)) {
            level++;
            toVisitQueue.add(inreaser);
            continue;
        }
        visited.add(currentNode);
        for (Integer child : graph.get(currentNode)) {
            if (!visited.contains(child)){
                toVisitQueue.add(child);
            }
        }
    }
    return false;
}

使代码 return 错误的部分如下：

public static void main(String[] args) {
    Basics x = new Basics();
    x.graph = new HashMap<>();

    Set<Integer> s = new HashSet<>();

    s.add(2);
    x.graph.put(1, s);

    s = new HashSet<>();
    s.add(1);
    s.add(3);
    x.graph.put(2, s);

    s = new HashSet<>();
    s.add(2);
    s.add(4);
    x.graph.put(3, s);

    s = new HashSet<>();
    s.add(3);
    s.add(5);
    x.graph.put(4, s);

    s = new HashSet<>();
    s.add(4);
    s.add(6);
    x.graph.put(5, s);

    s = new HashSet<>();
    s.add(5);
    x.graph.put(6, s);

    if (!x.initialCheck(1, 5)) {
        System.out.println("A new user is involved");
    } else {
        if (x.levelOneFriends(1, 5)) {
            System.out.println("friends");
        } else {
            System.out.println("not friends");
            if (x.levelTwoFriends(1, 5)) {
                System.out.println("friends level 2");
            } else {
                System.out.println("not friends of level 2");
                if (x.checkLevelBFS(1, 5)) {
                    System.out.println("YES - friends of level 4");
                } else {
                    System.out.println("NO - not friends of level 4");
                }
            }
        }
    }
    System.out.println(x.checkLevelBFS(1, 2));
    System.out.println(x.checkLevelBFS(1, 3));
    System.out.println(x.checkLevelBFS(1, 4));
    System.out.println(x.checkLevelBFS(1, 5));
    System.out.println(x.checkLevelBFS(1, 6));
}

输出：

not friends
not friends of level 2
NO - not friends of level 4
false
false
false
false
false

前两行是正确的输出，第三行不正确，因为 1 和 5 是 4 级的 fried，应该打印 YES -
下面的 'false' 输出也很奇怪！

'initialCheck' 检查两个用户中是否有任何一个不在图表中。
'levelOneFriends' 检查两个对象是否是直接朋友。
'levelTwoFriends' 检查两个对象是否在朋友的朋友关系中。

有什么帮助吗？

谢谢！

Answer 1

[在 OP 的评论显示 levelTwoFriends]

后编辑

public boolean levelTwoFriends(Integer user1, Integer user2) { 
  Collection<Integer> c = graph.get(user1);
  // c.retainAll(graph.get(user2)); 
  // return !c.isEmpty(); 

  // true only if a non-void intersection
  return false==Collections.disjoint(c, graph.get(user2));
}

或者，作为单行

public boolean levelTwoFriends(Integer user1, Integer user2) { 
  return false==Collections.disjoint( graph.get(user1), graph.get(user2) );
}

[使用 x.initialCheck 更新后编辑]

那么你的错误必须在 x.initialCheck 中，而你在实际进入 x.checkLevelBFS 之前正在做的其他事情。在邻接列表的内部表示中验证 x.initialCheck 和 x.levelOneFriends 是否被修改（那里必须是一个 - 运行在调试器中并保持关注内容的修改）。我为什么这样说？因为下面的代码按预期工作：

  static public void main(String[] args) {
    ExampleTest x=new ExampleTest(); // in your case, it's Basics

    x.graph=new HashMap<>();
    x.graph.put(1, new HashSet<>(Arrays.asList(2)));
    x.graph.put(2, new HashSet<>(Arrays.asList(1,3)));
    x.graph.put(3, new HashSet<>(Arrays.asList(2,4)));
    x.graph.put(4, new HashSet<>(Arrays.asList(3,5)));
    x.graph.put(5, new HashSet<>(Arrays.asList(4,6)));
    x.graph.put(6, new HashSet<>(Arrays.asList(5)));
    System.out.println(x.checkLevelBFS(1, 2)); // true
    System.out.println(x.checkLevelBFS(1, 3)); // true
    System.out.println(x.checkLevelBFS(1, 4)); // true
    System.out.println(x.checkLevelBFS(1, 5)); // true
    System.out.println(x.checkLevelBFS(1, 6)); // false
  }

"The problem is that my method always returns false!"

但事实并非如此！您的错误可能在其他地方！！！

我会将此标记为 对我有效 并关闭错误。

我的代码用于驱动测试。

class ExampleTest {
  Map<Integer, Set<Integer>> graph;  

  static public void main(String[] args) {
    ExampleTest x=new ExampleTest();
    x.graph=new HashMap<>();
    x.graph.put(1, new HashSet<>(Arrays.asList(2)));
    x.graph.put(2, new HashSet<>(Arrays.asList(3)));
    x.graph.put(3, new HashSet<>(Arrays.asList(4)));
    x.graph.put(4, new HashSet<>(Arrays.asList(5)));
    x.graph.put(5, new HashSet<>(Arrays.asList(6)));
    System.out.println(x.checkLevelBFS(1, 2)); // true
    System.out.println(x.checkLevelBFS(1, 3)); // true
    System.out.println(x.checkLevelBFS(1, 4)); // true
    System.out.println(x.checkLevelBFS(1, 5)); // true
    System.out.println(x.checkLevelBFS(1, 6)); // false
  }

  // verbatim copy of your method here
  public boolean checkLevelBFS(Integer source, Integer dest) {
    Queue<Integer> toVisitQueue = new LinkedList<>(graph.get(source));
    Set<Integer> visited = new HashSet<>();
    visited.add(source);
    Integer inreaser = new Integer(-1); // indicator for level increase
    toVisitQueue.add(inreaser);
    int level = 1; // because we already passed the source and started from its children nodes
    while (level <= 4 && !toVisitQueue.isEmpty()) {
      Integer currentNode = toVisitQueue.remove();
      if (currentNode.equals(dest)) {
        return true;
      }
      if (visited.contains(currentNode)) {
        continue;
      }
      if (currentNode.equals(inreaser)) {
        level++;
        toVisitQueue.add(inreaser);
        continue;
      }
      visited.add(currentNode);
      for (Integer child : graph.get(currentNode)) {
        if (!visited.contains(child)){
          toVisitQueue.add(child);
        }
      }
    }
    return false;
  }

}

JAVA - BFS 到图中有限的友谊级别

JAVA - BFS to a limited friendship level in a graph

algorithm

graph

breadth-first-search