PLEASE WRITE IN JAVA Lab 10 Graph Objective: Create a class which constructs a g
ID: 3683704 • Letter: P
Question
PLEASE WRITE IN JAVA
Lab 10
Graph
Objective:
Create a class which constructs a graph and performs a few graph operations. Test out your code with the driver.
Download the class called Graph from here. It already has some instance variables and constructors. It is up to you to finish it by adding the following methods.
addVertex: this method which returns nothing and takes in a string parameter corresponding to the name of the new vertex. It will only add a new vertex if that name is not already in the list of vertices.
vertexIsContained: this method returns a true or false if there exists a vertex in the graph that matches the name passed in via the parameter.
addEdge: this method returns nothing and takes in two string parameters and a weight. The two string parameters correspond to the names of vertices and the weight is the weight of the newly created edge. The newly created edge is then placed in the neighbor’s edge list inside the first vertex. If either the first or second vertex doesn’t exist the method should not continue.
getVertex: this method returns an instance of a vertex if the name (passed in via a parameter) is found in the vertex list.
printDFS: This prints out the vertices name’s in depth first order. You can find the algorithm the presentation provided.
printBFS: This prints out the vertices name’s in breadth first order. Like above you can find the algorithm in the presentation.
printLazyDFS: In the class there is an instance variable called maxDist which corresponds to the maximum distance that is allowed to travel. Write another DFS but make sure it doesn’t traverse edges that are greater than the max distance.
Here’s the graph class
Heres the driver class
Here’s the graph the driver is based on
Example Print Out:
Adding verticies
Adding edges
Printing DFS
v1
v2
v4
v7
v6
v8
v5
v3
Printing BFS
v1
v2
v4
v6
v5
v7
v8
v3
Printing Lazy DFS
v1
v2
v4
v7
v6
Explanation / Answer
package graphs; import java.util.*; import graphs.State; public class Implementgraph { public void depthfirstsearch(Node root) { //This is basically done to avoid infinite loops if(root == null) return; System.out.print(root.getVertex() + " "); root.state = State.Visited; //This is done for every childfor every child for(Node n: root.getChild()) { //however if childs state is not visited then we will recurse if(n.state == State.Unvisited) { depthfirstssearch(n); } } } public void breadthfirstsearch(Node root) { Queue queue = new LinkedList(); if(root == null) return; root.state = State.Visited; //This will add root to end of queue queue.add(root); while(!queue.isEmpty()) { //This will remove the node from front of queue Node p = queue.remove(); System.out.print(p.getVertex() + " "); //now we will visit child first before grandchild for(Node n: p.getChild()) { if(n.state == State.Unvisited) { queue.add(n); n.state = State.Visited; } } } } public static Graph createaNewGraphhere() { Graphhere g = new Graphhere(); Node[] temporary = new Node[8]; temporary[0] = new Node("A", 3); temporary[1] = new Node("B", 3); temporary[2] = new Node("C", 1); temporary[3] = new Node("D", 1); temporary[4] = new Node("E", 1); temporary[5] = new Node("F", 1); temporary[0].addaChildnode(temporary[1]); temporary[0].addaChildNode(temporary[2]); temporary[0].addaChildNode(temporary[3]); temporary[1].addaChildNode(temporary[0]); temporary[1].addaChildNode(temporary[4]); temporary[1].addaChildNode(temporary[5]); temporary[2].addaChildNode(temporary[0]); temporary[3].addaChildNode(temporary[0]); temporary[4].addaChildNode(temporary[1]); temporary[5].addaChildNode(temporary[1]); for (int i = 0; i < 7; i++) { g.addaNodehere(temporary[i]); } return g; } public static void main(String[] args) { Graphhere gDfs = createaNewGraphhere(); Implementgraph s = new Implementgraph(); System.out.println("implement DFS"); s.depthfirstsearch(gDfs.getNode()[0]); System.out.println(); System.out.println(); Graphhere gBfs = createaNewGraphhere(); System.out.println("implement BFS"); s.breadthfirstssearch(gBfs.getNode()[0]); } } Graphhere.java // to implement a graph with vertices and adding nodes package graphs; public class Graphhere { public int countvertices; private Node vertices[]; public Graphhere() { vertices = new Node[8]; countvertices = 0; } public void addaNodehere(Node n) { if(count < 10) { vertices[countvertices] = n; countverticest++; } else { System.out.println("graph full"); } } public Node[] getNode() { return vertices; } } NODE CLASS.JAVA:// to implement the nodes with vertices private String vertex; public State state; public Node(String vertex) { this.vertex = vertex; } public Node(String vertexhere, int childlen) { this.vertex = vertexhere; childCount = 0; child = new Node[childlen]; } public void addaChildNode(Node adjhere) { adjhere.state = State.Unvisited; if(childCount < 30) { this.child[childCount] = adj; childCount++; } } public Node[] getChild() { return child; } public String getVertex() { return vertex; } package graphs; import java.util.*; import graphs.State; public class Implementgraph { public void depthfirstsearch(Node root) { //This is basically done to avoid infinite loops if(root == null) return; System.out.print(root.getVertex() + " "); root.state = State.Visited; //This is done for every childfor every child for(Node n: root.getChild()) { //however if childs state is not visited then we will recurse if(n.state == State.Unvisited) { depthfirstssearch(n); } } } public void breadthfirstsearch(Node root) { Queue queue = new LinkedList(); if(root == null) return; root.state = State.Visited; //This will add root to end of queue queue.add(root); while(!queue.isEmpty()) { //This will remove the node from front of queue Node p = queue.remove(); System.out.print(p.getVertex() + " "); //now we will visit child first before grandchild for(Node n: p.getChild()) { if(n.state == State.Unvisited) { queue.add(n); n.state = State.Visited; } } } } public static Graph createaNewGraphhere() { Graphhere g = new Graphhere(); Node[] temporary = new Node[8]; temporary[0] = new Node("A", 3); temporary[1] = new Node("B", 3); temporary[2] = new Node("C", 1); temporary[3] = new Node("D", 1); temporary[4] = new Node("E", 1); temporary[5] = new Node("F", 1); temporary[0].addaChildnode(temporary[1]); temporary[0].addaChildNode(temporary[2]); temporary[0].addaChildNode(temporary[3]); temporary[1].addaChildNode(temporary[0]); temporary[1].addaChildNode(temporary[4]); temporary[1].addaChildNode(temporary[5]); temporary[2].addaChildNode(temporary[0]); temporary[3].addaChildNode(temporary[0]); temporary[4].addaChildNode(temporary[1]); temporary[5].addaChildNode(temporary[1]); for (int i = 0; i < 7; i++) { g.addaNodehere(temporary[i]); } return g; } public static void main(String[] args) { Graphhere gDfs = createaNewGraphhere(); Implementgraph s = new Implementgraph(); System.out.println("implement DFS"); s.depthfirstsearch(gDfs.getNode()[0]); System.out.println(); System.out.println(); Graphhere gBfs = createaNewGraphhere(); System.out.println("implement BFS"); s.breadthfirstssearch(gBfs.getNode()[0]); } } Graphhere.java // to implement a graph with vertices and adding nodes package graphs; public class Graphhere { public int countvertices; private Node vertices[]; public Graphhere() { vertices = new Node[8]; countvertices = 0; } public void addaNodehere(Node n) { if(count < 10) { vertices[countvertices] = n; countverticest++; } else { System.out.println("graph full"); } } public Node[] getNode() { return vertices; } } NODE CLASS.JAVA:// to implement the nodes with vertices private String vertex; public State state; public Node(String vertex) { this.vertex = vertex; } public Node(String vertexhere, int childlen) { this.vertex = vertexhere; childCount = 0; child = new Node[childlen]; } public void addaChildNode(Node adjhere) { adjhere.state = State.Unvisited; if(childCount < 30) { this.child[childCount] = adj; childCount++; } } public Node[] getChild() { return child; } public String getVertex() { return vertex; }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.