java - 遍历图的顶点作为该顶点的方法

Question

我有一个目前无法解决的问题。

假设我有一个类 Member ，包含有关与给定成员相关的成员列表的信息: ArrayList<Member> links;

另外，这个类还有一个方法叫canBeLinked(Member member) ,

这显然返回 boolean 值，定义特定成员是否可以直接或间接地与给定成员链接。

“直接”是指公共(public)关系 A -> B；如果例如A -> B，和 B -> C，那么它也应该返回 true。还要记住，如果 A -> B，则 B -> A。这样我们就得到了一个无向图的模型。

我的困惑是如何实现这个功能；我想它一定是递归的，但重点是它不是两个参数的函数(例如，如果它是静态函数，我们可以轻松编写函数 canBeLinked(Member a, Member b) ，互联网上有很多此类图的实现)。

我的第一个方法是写这样的东西:

public boolean canBeLinked(Member member) {
   if (this.links.contains(member)) {
       return true;
   }
   else {
       for (Member m : links)
           if (m.canBeLinked(member)) return true;
   }
   return false;
}

我肯定会得到 StackOverflowException； 假设我们有这样的关系:

A -> B
B -> D
B -> E
D -> C
E -> C

调用时

a.canBeLinked(c) 

我们得到: 1)首先我们检查“c”是否已经在“a”的成员列表中； 2)这是不正确的，所以进入for循环； 3) 因为列表中只有一个成员(它是“b”)，所以我们调用 b.canBeLinked(c)； 4) "c"也不是 "b"列表的成员，所以它也进入 "for"语句 5) 现在我们有麻烦了，因为“b”的列表不仅包含“e”和“d”，还包含“a”，这导致我们到 p.1；它会永远持续下去(直到内存耗尽)

您能解释一下如何解决这个问题吗？我很确定这是一个简单的问题，但我只是坚持了下来，并且肯定遗漏了其中的一些关键点。

Answer 1

幸运的是修复相当简单；你需要跟踪哪个Members在您的搜索中已经访问过，例如使用 Set<Member> , 而不是循环返回访问任何 Members已经看到了。查询链接前Members您添加当前 Member到访问的集合。

由于您的递归函数现在需要传递访问成员集，因此最好将其拆分为 private或 protected您从公共(public)方法调用的方法。

public boolean canBeLinked(Member member) 
{
  return canBeLinked(member, new HashSet<>());
}

private boolean canBeLinked(Member member, Set<Member> visited)
{
  if (this.links.contains(member)) {
      return true;
  }
  else {
    visited.add(this);
    for (Member m : links)
    {
      if (!visited.contains(m)) return m.canBeLinked(member, visited);
    }
  }
  return false;
}