Suppose you have a map of software packages and dependencies:
A depends on B, C
B depends on D, E, F
C depends on F
F depends on G
H depends on I, J
J depends on G
Write a class or method that can install an individual package, along with dependencies.
Assume every individual package has an "install()" method to install the package without its dependencies.
For instance, to install package A
installWithDependencies(A) will produce G,F,C,E,D,B,A
Directed Acyclic Graph.
Order is not the same as in output, but all characters are there, any thoughts?
public class Dependencies {
static List<Character> findDependencies(Map<Character, ArrayList<Character>> graph, Character c){
List<Character> result = new ArrayList<>();
Set<Character> visited = new HashSet<>();
Queue<Character> queue = new LinkedList<>();
queue.add(c);
visited.add(c);
while(!queue.isEmpty()){
Character ch = queue.remove();
result.add(ch);
List<Character> list = graph.get(ch);
if(list == null)
continue;
for(Character cha: list){
if(!visited.contains(cha)){
queue.add(cha);
visited.add(cha);
}
}
}
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
Map<Character, ArrayList<Character>> map = new HashMap<>();
map.put('A', new ArrayList<>(List.of('B','C')));
map.put('B', new ArrayList<>(List.of('D','E','F')));
map.put('C', new ArrayList<>(List.of('F')));
map.put('F', new ArrayList<>(List.of('G')));
map.put('H', new ArrayList<>(List.of('I','J')));
map.put('J', new ArrayList<>(List.of('G')));
System.out.println(findDependencies(map, 'A'));
}
}
Output: [G, F, E, D, C, B, A]
Expected Output: [G, F, C, E, D, B, A]Comments (8)