Answered: You will implement some methods in the…

Related questions

Question

You will implement some methods in the UndirectedGraph class. The UndirectedGraph class contains two nested classes, Vertex and Node, you should NOT change these classes. The graph will store a list of all the vertices in the graph. Each vertex has a pointer to its adjacent vertices. To get started, import the starter file, Undirected.java into the graphs package you create in a new Java Project. Please do not change any of the method signatures in the class, but you can add any helper methods you deem necessary. Implement the methods described below. You are free to test your code however you prefer.

Vertex Class (DO NOT EDIT)
The vertex class holds information about the vertices in the graph. It has an int val, a Vertex next that refers to the next vertex in the list of vertices (not necessarily an adjacent vertex), and a Node edge that starts the list of adjacent vertices.

Node Class (DO NOT EDIT)
This is a simple class to represent an adjacency list of a vertex in the graph.

UndirectedGraph Class
You will implement the following methods in the UndirectedGraph class.

public boolean addEdge(int val1, int val2)

This method adds an undirected edge between the Vertex with val equal to val1 and the Vertex with val equal to val2. You can assume that there exists vertices with vals equal to val1 and val2 (i.e., there are Vertex objects in the vertices list that have vals equal to val1 and val2). The Nodes in the edge list should be stored in ascending order by vert.val. This method returns false if the edge already exists and true if the edge was added. You might want a helper method here that can find a vertex with val v. Hint: that this is an undirected graph so you should create an edge from the Vertex with val1 to the Vertex with val2 and vice versa.

public ArrayList<Integer> breadthFirstSearch(int initial)
This method should return an ArrayList of integers corresponding to the values associated with the vertices in the graph visited in breadth first order. You can assume that the graph contains a vertex with value initial. Instead of changing the colors of the nodes we will keep track of the values of the nodes we've visited in the visited ArrayList. You must implement this using a queue.

Below is method siganture class:

package graphs;

import java.util.*;

public class UndirectedGraph {

static class Vertex {
int val;
Vertex next; //next vertex in the list
Node edge; //pointer to first edge

Vertex(int u,Vertex next){
val = u;
this.next = next;
edge = null;
}

//helpful for printing and debugging
public String toString() {
String s = val+"->";
Node node = edge;
while(node!=null) {
s = s+ node.vert.val+",";
node = node.next;
}
return s.substring(0,s.length()-1);

}

}
static class Node {
Vertex vert;
Node next;

Node(Vertex v, Node next){
this.vert = v;
this.next = next;
}
}

Vertex vertices;//pointer to first vertex in the graph (vertex with the smallest val)

public UndirectedGraph() {
vertices = null;
}