234

Answers

32

Questions

Top answer(5)

// Java Code import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Scanner; public class InDDegrees { /** * The below functions returns a list of people who are within * D degrees of separation from 'Person' * The Algorithm used is BFS ('Breadth First Search') */ public static ArrayList findFriends(Map graph, int D, String Person){ ArrayList friends = new ArrayList(); // Queue for running BFS Queue curList = new LinkedList(); curList.add(Person); // visitedPersons contain the list of all the persons visited so far in BFS // the value for 'key' is the degree of separation from 'Person' Map visitedPersons = new HashMap(); visitedPersons.put(Person,0); while(!curList.isEmpty()) { String curPerson = curList.poll(); Integer degree = visitedPersons.get(curPerson); if(degree >= D) { break; } //find the persons who are known to 'curPerson' if(graph.get(curPerson) != null) { ArrayList knownToCurPerson = graph.get(curPerson); for(String p : knownToCurPerson) { // if 'p' doesn't exist in visited, add 'p' to visited and queue if(!visitedPersons.containsKey(p)) { visitedPersons.put(p,degree+1); curList.add(p); } } } } // put all the keys for which value >=1 in 'friends' for(String p : visitedPersons.keySet()) { if(visitedPersons.get(p) > 0) friends.add(p); } return friends; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); ArrayList relationships = new ArrayList(); String s = in.nextLine(); while(!s.equals("done")) { relationships.add(s); s = in.nextLine(); } ArrayList queries = new ArrayList(); s = in.nextLine(); while(!s.equals("done")) { queries.add(s); s = in.nextLine(); } // now build a directed graph using relationship List // The Directed graph is stored as a Map. Map< String, ArrayList > graph = new HashMap< String, ArrayList>(); // the Key consists of name of a person (e.g "Alice","Bob" etc) // the value consists of an ArrayList which contains the all the persons known to 'key' for (String r:relationships) { // Assuming that 'r' is of the form " knows " String[] names = r.split(" "); // the first and third string would be the names of the persons String key = names[0]; if(!graph.containsKey(key)) { ArrayList val = new ArrayList(); val.add(names[2]); graph.put(key, val); }else { ArrayList val = graph.get(key) ; val.add(names[2]); graph.replace(key, val); } } // Now get queries for (String q : queries) { // Assuming that 'q' is of the form " knows " String[] query = q.split(" "); int degree = Integer.parseInt(query[0]); String person = query[1]; System.out.println(person + " is within " + query[0] + " degrees of separation from:"); ArrayList knownPersons = findFriends(graph, degree, person); // sort the list 'knownPersons' and then print the contents Collections.sort(knownPersons); for(String per : knownPersons){ System.out.println(" "+per); } } in.close(); } } ------------------------------------------------------------------------------------------------------
0 like
0 comment