Java: Trouver des chaînes d'amitié via la récursivité

Question

Java: Trouver des chaînes d'amitié via la récursivité

Je travaille actuellement sur un problème où je dois trouver des chaînes d'amitié via la récursivité en Java. Statistiquement, une personne connaît une autre personne sur environ 6 waypoints - qui est la chaîne que j'essaie de trouver.

J'ai une classe "Personne", qui définit un nom et des amis directs:

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

Un diagramme a été donné qui donne un exemple de chaîne, où les flèches indiquent une relation unidirectionnelle ou bidirectionnelle (comme dans Thomas connaît Theresa, mais Theresa ne sait pas Thomas):

Donc, fondamentalement, mon résultat devrait ressembler à quelque chose comme ceci:

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

J'ai fait beaucoup de programmation récursive dans le passé, mais je ne peux tout simplement pas me mettre la tête dedans en ce moment - j'apprécierais toute aide!

1

French java recursion

Author: Tekumi, 2016-11-18

Source

1 answers

score 1 · Accepted Answer

Voici un exemple, mais attention, cela ne fonctionnera que si votre graphique n'a qu'un seul chemin, comme dans votre exemple d'image

Si ce n'est pas assez large pour répondre à vos besoins, au moins les première et deuxième étapes (peut-être la troisième aussi) devraient être utiles:

1) Vous n'acceptez friendsChain dans le constructeur de Person, mais comment pouvez-vous passer une chaîne de Person objets qui n'ont pas encore été créé ? C'est une dépendance de création cyclique; je suggère de supprimer le problème avec un constructeur plus léger, avec un setter pour friendChain.

public Person(final String name) {

    this.name = name;
}

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

2) Construisons des objets Person et peuplons leurs chaînes d'amis

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) Construisons une méthode récursive pour suivre la chaîne d'amis (notez que nous utilisons un List, car nous ne connaissons pas la taille finale de la chaîne):

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) Appelez-le:

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

getFriendshipChain(adam, theresa, result);

System.out.println(result);