2016-11-18 97 views
1

我目前正在研究一個問題,我必須通過Java中的遞歸找到友情鏈。統計上,一個人在大約6個航點上認識另一個人 - 這是我試圖找到的鏈條。Java:通過遞歸尋找友誼鏈

我有一類「人」,它定義了一個名稱和直接的朋友:

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

給出的圖是給出了一個例子鏈,在箭頭所指的單向或雙向關係(如托馬斯知道特蕾莎,但特里薩不知道托馬斯): Example chain

所以基本上我的成果應該類同是這樣的:

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 

過去我已經做了很多遞歸編程,但我現在無法讓我的頭腦進入 - 我會很感激任何幫助!

+1

你不應該考慮鏈條,而是根據圖表。找一個圖庫,讓每個人都是一個頂點,每一個友誼都是一個邊緣,並要求它獲得最短的路徑。既然你談到方向,你應該找到一個有針對性的圖/ –

+0

有關'Person#equals'的一些事情。首先你需要[滿足合同](http://stackoverflow.com/questions/3181339/right-way-to-implement-equals-contract)。其次,你需要[重寫'hashcode'](http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java)。最後,你應該在'isFriendsWith'中使用它。 – bradimus

+0

你爲什麼期望'結果[2]'只返回托馬斯?根據你的圖表,Krestin是Michael和Thomas的朋友,在穿越你的道路時不應該考慮這個問題嗎? – px06

回答

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

我只接受構造函數中的friendsChain,因爲「Person」類被授予了我 - 我不會那樣做,而且你是完全正確的。 你給了一個很棒的解釋,我完全理解它的一切,並將使用你的代碼來獲得解決方案,然後我將在這裏發佈。謝謝你的努力! – Tekumi