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）您只接受在Person構造friendsChain，但你怎麼能傳遞尚未創建Person對象鏈？ 這是一個循環創建依賴項;我建議用一個更輕的構造函數來解決這個問題，以及一個friendChain的setter。

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