Java: Поиск цепочек дружбы через рекурсию

Question

В настоящее время я работаю над проблемой, когда мне нужно найти цепи дружбы через рекурсию на Java. По статистике, человек знает другого человека примерно по 6 путевым точкам - это цепь, которую я пытаюсь найти.

У меня есть класс «Человек», который определяет имя и прямых друзей:

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) вы только принимаете в конструкторе PersonfriendsChain, но как вы можете пройти цепочку Person объектов, которые еще не были созданы? Это циклическая зависимость создания; Я предлагаю удалить проблему с помощью более легкого конструктора вместе с установщиком для friendChain.

public Person(final String name) { 

    this.name = name; 
} 

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

2) Давайте строить Person объектов и заполнить их друг цепь

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);