六度分离算法

Question

我遇到了一个问题，我们需要使用最短路径来计算朋友之间的分离程度。我想到了dfs方法，然后必须从每个朋友那里创建一个新列表，以找出最小的列表。我正在考虑使用Trie数据结构来保留朋友和他们的朋友，但是有没有简单的解决方法，可以提供任何指导。

这是我得到的Java类。

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * Implement the function in this class that will
 */
public class FriendFinder {

    private final SocialNetworkService sns;

    FriendFinder(SocialNetworkService socialNetworkService) {

        sns = socialNetworkService;
    }

    /**
     * Returns an ordered list of connectivity if the given personAId has a connection of friend relationships to personZId
     * within the specified degreesOfSeparation, otherwise return null.
     */
    public List<String> findShortestPath(String personAId, String personZId, int degreesOfSeparation) {

        // TODO: Implement this function by calling the 'injected' SocialNetworkService to search friends of the Person Ids...
        List<String> list = new ArrayList<>();
        list.add(personAId);
        dfs(personAId,personZId,0,degreesOfSeparation,list);
        return list;
    }

   public void dfs(String personA, String personZ, int depth, int degreesOfSeparation, List<String> list){
        if(depth > degreesOfSeparation){
            return;
        }
        if(personA.equals(personZ)){
            list.add(personZ);
            return;
        }
        else{
            Collection<String> friends = sns.findFriends(personA);
            for(String friend: friends){
                if(!list.contains(friend)){
                    list.add(friend);
                    if(friend.equals(personZ)) return;
                    depth += 1;
                    dfs(friend, personZ, depth, degreesOfSeparation, list);
                    if(list.contains(personZ)) return;
                }

            }

        }
    }

}

import java.util.Collection;

public interface SocialNetworkService {

    /**
     * Returns a set of Ids of the immediate friends of the Person with the given Id.
     */
    Collection<String> findFriends(String personId);

    /**
     * Creates a new Person in the social network with the given name and returns the unique Id of the Person.
     */
    void addPerson(String personId);

    /**
     * Adds a friend relationship between the given two Person Ids
     */
    void addFriend(String personId, String friendId);
}

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class FriendFinderTest {

    @Test
    public void findRelationshipPathBonusQuestionTest() {

        SNSImpl sns = new SNSImpl();
        sns.addFriend("Kevin", "UserB");
        sns.addFriend("Kevin", "UserS");
        sns.addFriend("UserB", "UserC");
        sns.addFriend("UserA", "UserD");
        sns.addFriend("UserX", "UserC");
        sns.addFriend("UserY", "UserX");
        sns.addFriend("Bacon", "UserY");

        FriendFinder ff = new FriendFinder(sns);

        Assert.assertEquals(ff.findShortestPath("Kevin", "Bacon", 5),
                Arrays.asList("Kevin", "UserB", "UserC", "UserX", "UserY", "Bacon"));

        // Create a shorter path that will be accessed later in the return collection (list in this test case) of friends
        sns.addFriend("UserS", "Bacon");
        Assert.assertEquals(ff.findShortestPath("Kevin", "Bacon", 6),
                Arrays.asList("Kevin", "UserS", "Bacon"));
    }
}

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

public class SNSImpl implements SocialNetworkService {

    HashMap<String, Collection<String>> relationships = new HashMap<>();

    /**
     * Returns a list of Ids of the immediate friends of the Person with the given Id.
     */
    @Override
    public Collection<String> findFriends(String personId) {

        return relationships.get(personId);
    }

    /**
     * Creates a new Person in the social network with the given name and returns the unique Id of the Person.
     */
    @Override
    public void addPerson(String personId) {

        relationships.put(personId, new ArrayList<>());
    }

    /**
     * Adds a friend relationship between the given two Person Ids
     */
    @Override
    public void addFriend(String personId, String friendId) {

        // Ensure that both persons exist in the map for convenience.

        if (!relationships.containsKey(personId)) {
            addPerson(personId);
        }

        if (!relationships.containsKey(friendId)) {
            addPerson(friendId);
        }

        relationships.get(personId).add(friendId);
        relationships.get(friendId).add(personId);
    }
}

新年快乐，新年快乐...

Answer 1

DFS找不到最短的路径，它仅对找出是否存在路径非常有用。 （DFS只是找到一条对其长度没有任何限制的路径）

BFS是您需要的。拳头找到的路径也是最短的路径（可能还有其他长度相同的路径）。