遍历图的顶点作为该顶点的一种方法

Question

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

假设我有一个 class Member，其中包含有关与给定成员相关联的成员列表的信息： ArrayList<Member> links;

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

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

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

我的困惑是如何实现这个功能；我想它一定是递归的，但关键是它不是两个参数的函数（例如，如果它是静态函数，我们可以很容易地编写 function 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在您的搜索中已经访问过的内容，例如使用 a Set<Member>，而不是循环返回访问任何Members已经看过的内容。在查询链接之前，Members您将当前添加Member到访问的集合中。由于您的递归函数现在需要传递访问过的成员集，因此最好将其拆分为您从公共方法调用的privateorprotected方法。public boolean canBeLinked(Member member)&nbsp;{&nbsp; return canBeLinked(member, new HashSet<>());}private boolean canBeLinked(Member member, Set<Member> visited){&nbsp; if (this.links.contains(member)) {&nbsp; &nbsp; &nbsp; return true;&nbsp; }&nbsp; else {&nbsp; &nbsp; visited.add(this);&nbsp; &nbsp; for (Member m : links)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; if (!visited.contains(m)) return m.canBeLinked(member, visited);&nbsp; &nbsp; }&nbsp; }&nbsp; return false;}