Java:通过递归查找友谊链

Question

我目前正在解决一个问题，我必须通过 Java 中的递归找到友谊链。据统计，一个人通过大约 6 个路径点认识另一个人 - 这就是我试图找到的链条。

我有一个“Person”类，它定义了名称和直接 friend :

public class Person
{
    private Person[] friendChain;
    private String name;

    public Person(String name, Person[] friendChain)
    {
        this.friendChain    = friendChain;
        this.name           = name;
    }

    public Person[] getFriends()
    {
        return this.friendChain;
    }

    public String getName()
    {
        return this.name;
    }

    public boolean isFriendWith(Person person)
    {
        for(Person p: this.friendChain)
        {
            if(p != null && person != null && p.getName().equals(person.getName())) 
                return true;
        }

        return false;
    }

    public boolean equals (Person person)
    {
        return this.name.equals(person.getName());
    }

    public String toString()
    {
        return this.getName();
    }
}

给出了一个图表，给出了示例链，其中箭头表示单向或双向关系(如托马斯认识特蕾莎，但特蕾莎不认识托马斯):

所以基本上我的结果应该类似于这样:

result = getFriendshipChain(adam, theresa);

result[0].getName(); // "Michael"
result[1].getName(); // "Kerstin"
result[2].getName(); // "Thomas"
result[3].getName(); // "Theresa"
result[4].getName(); // null
result[5].getName(); // null

我过去做过很多递归编程，但我现在无法理解这一点 - 我将不胜感激任何帮助!

Answer 1

这是一个示例，但请注意，只有当您的图表只有一条路径(如示例图像中所示)时，这才有效

如果这还不够广泛，无法满足您的需求，至少第一步和第二步(也许还有第三步)应该会有帮助:

1) 你只在 Person 的构造函数中接受 friendsChain ，但是你怎么能传递一个没有接受过的 Person 对象链呢？尚未创建？这是一个循环创建依赖；我建议使用更轻的构造函数以及 friendChain 的 setter 来消除问题。

public Person(final String name) {

    this.name = name;
}

public void setFriendChain(final Person[] friendChain) {
    this.friendChain = friendChain;
}

2) 让我们构建 Person 对象并填充他们的 friend 链

Person adam = new Person("Adam");
Person michael = new Person("Michael");
Person kerstin = new Person("Kerstin");
Person thomas = new Person("Thomas");
Person theresa = new Person("Theresa");

Person[] adamsFriends = { michael, kerstin };
adam.setFriendChain(adamsFriends);

Person[] michaelsFriends = { adam, kerstin };
michael.setFriendChain(michaelsFriends);

Person[] kerstinsFriends = { thomas, adam, michael };
kerstin.setFriendChain(kerstinsFriends);

Person[] thomasFriends = { kerstin, theresa };
thomas.setFriendChain(thomasFriends);

Person[] theresasFriends = { thomas };
theresa.setFriendChain(theresasFriends);

3) 让我们构建一个递归方法来跟踪好友链(请注意，我们使用 List，因为我们不知道链的最终大小):

public void getFriendshipChain(final Person from, final Person to, final List<Person> friendshipChain) {

    friendshipChain.add(from);

    // We have found the target person, return
    if (from.equals(to)) {
        return;
    }

    // For every friend from that person
    for (Person friend : from.getFriendChain()) {

        // If we don't already have it in the list
        if (!friendshipChain.contains(friend)) {

            // follow this friend's chain
            getFriendshipChain(friend, to, friendshipChain);

        }
    }

}

4)调用它:

List<Person> result = new ArrayList<Person>();

getFriendshipChain(adam, theresa, result);

System.out.println(result);