Six Degrees Of Separation Algorithm

I got a problem where we need to use the shortest path to calculate the degrees of separation between friends. I thought of dfs approach and then from every friend I have to create a new list to figure out the smallest list. I am thinking of Trie data structure to keep the friends and their friends, but is there any simple approach to solve it, any guidance is appreciated.

here are the java classes I got.

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

Best and happy new year...

DFS does not find the shortest path, it is only useful to find out if there is a path at all. (DFS just finds a path without any restrictions about its length)

BFS is what you need. The fist found path is also the shortest one (There might be other paths with the same length).