Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
ou 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

ou 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

icon
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 three methods in the UndirectedGraph class.

public boolean addVertex(int value)
This method adds a new vertex with val attribute equal to value. It returns true if the vertex is added and false if a vertex with val equal to value already exists. The vertex list (stored in the vertices instance variable) is kept in sorted order based on the value (smallest to largest).


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.

Below is method siganure 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;
    }


    public boolean addVertex(int value) {
        //add a new vertex with val value
        //return true if a vertex is added
        //return false if a vertex with val value already exists
        //the vertex list is kept in sorted order based on the value (smallest to largest)
        
        return true;
    }

    

 

    public boolean addEdge(int val1, int val2) {
        //You can assume there exists vertices with vals equal to val1 and val2
        //(i.e., there are Vertex objects in vertices that have vals equal to val1 and val2
        //You might want a helper method here that can find a vertex with val v
        //The Nodes in the edge list should be stored in ascending order by vert.val
        //If the edge already exists return false
        //Note that this is an undirected graph so you should create an edge from
        //val1 to val2 and val2 to val1.
        return true;
    }

//String representation of the graph
    public String toString() {
        String s = "";
        Vertex vert = vertices;
        while(vert!=null) {
            s = s + vert.toString() + "\n";
            vert = vert.next;
        }
        return s;
    }


}

Example Suppose I have the below graph. oso 2 Represented in the UndirectedGraph class as... vertices val 1 edge next vert next vert val 2 edge next vert next vert next vert val edge next val edge 3-4 vert 1 The breadthFirstSearch with argument equal to 3 would result in the following ArrayList: [3,2,1,4] vert next vert
Transcribed Image Text:Example Suppose I have the below graph. oso 2 Represented in the UndirectedGraph class as... vertices val 1 edge next vert next vert val 2 edge next vert next vert next vert val edge next val edge 3-4 vert 1 The breadthFirstSearch with argument equal to 3 would result in the following ArrayList: [3,2,1,4] vert next vert
Expert Solution
steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer