Answered step by step
Verified Expert Solution
Question
1 Approved Answer
How do explain the Big O runtime/space efficiency of my Java code? I would like a very detailed explanation! //GraphWD.java interface import java.util.List; public interface
How do explain the Big O runtime/space efficiency of my Java code? I would like a very detailed explanation!
//GraphWD.java interface import java.util.List; public interface GraphWD{ public void addVertex(T vertex); public void addEdge(T src, T dest, int weight); public List neighbors(T vertex); public List getVertices(); public int familyMembers(T peep); } //Family.java public class Family { private String name; public Family(String name) { this.name = name; } public String getName() { return name; } @Override public String toString() { return name; } } //AdjList.java import java.util.ArrayList; import java.util.HashMap; import java.util.List; public class AdjList implements GraphWD { private int[][] graph; private HashMap map = new HashMap<>(); private HashMap reverseMap = new HashMap<>(); private int count = 0; public AdjList(int numVertices) { graph = new int[numVertices][numVertices]; } @Override public void addVertex(T vertex) { map.put(vertex, count); reverseMap.put(count++, vertex); } @Override public void addEdge(T src, T dest, int weight) { int srcIndex = map.get(src); int destIndex = map.get(dest); graph[srcIndex][destIndex] = weight; } @Override public List neighbors(T vertex) { int index = map.get(vertex); List neighbors = new ArrayList<>(); for (int i = 0; i < graph.length; i++) { if (graph[index][i] != 0) { neighbors.add(reverseMap.get(i)); } } return neighbors; } public int familyMembers(T peep){ int count = 0; int index = map.get(peep); for(;index allVertices = new ArrayList<>(map.keySet()); return allVertices; } } //TreeDriver.java import java.util.List; import java.util.Scanner; public class TreeDriver { public static void main(String[] args) { GraphWD member = new AdjList<>(30); // number can be changed int tree=0; // 1st gen Family A = new Family("Susan"); // 2nd gen Family B = new Family("Ian"); Family C = new Family("Anthony"); member.addVertex(A); member.addVertex(B); member.addVertex(C); member.addEdge(A, B,1); member.addEdge(A, C,1); //3rd gen Family D = new Family("Felix"); Family E = new Family("Jack"); Family F = new Family("Charlie"); member.addVertex(D); member.addVertex(E); member.addVertex(F); member.addEdge(B, D,2); member.addEdge(B, E,2); member.addEdge(C, F,2); List allPeople = member.getVertices(); while(true){ System.out.println("Welcome to your Family Tree!"); System.out.println("What would you like to do?:"); System.out.println("1). Display family tree."); System.out.println("2). Search for a member."); System.out.println("3). Search for a member's parents."); System.out.println("4). Search for a member's children."); System.out.println("5). Search for a member's siblings."); System.out.println("6). Display the number of members."); System.out.println("Click ENTER to exit."); //taking choice as input Scanner sc = new Scanner(System.in); String fam = sc.nextLine(); if(fam.equals("")){ break; } switch(fam){ case "1":{ for(Family each : allPeople){ System.out.println(each.getName() + "'s kids"); System.out.println(member.neighbors(each)); System.out.println(); } break; } case "2":{ System.out.println("Enter a name to search"); Scanner sc1 = new Scanner(System.in); String s = sc1.nextLine(); int tree1=0; for (Family each : allPeople) { if(s.equals(each.getName())){ System.out.println(s + " found in family"); tree1++; break; } } if(tree1==0){ System.out.println("Person not found"); } break; } case "3":{ System.out.println("Enter name to search for parents"); Scanner sc2 = new Scanner(System.in); String s = sc2.nextLine(); int tree1 = 0; for(Family each : allPeople){ for(int j=0;j =0){ for(j=0;j
Step by Step Solution
★★★★★
3.36 Rating (143 Votes )
There are 3 Steps involved in it
Step: 1
AdjList Class Constructor AdjListint numVertices Time Complexity O1 Space Complexity On2 where n is ...Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started