CodeWorkout
  1. Home
  2. Gym
  3. Practice In-Class Quiz 4
  4. X1600: Write method hasEdge in adjacency list

X1600: Write method hasEdge in adjacency list

Description

You are been given a partially implemented GraphAdjList class that represents an unweighted, undirected graph using an adjacency-list structure.

  • The graph stores its adjacency lists in an array of ArrayList<Integer>, where each index corresponds to a node.
  • If the graph has n nodes, then the instance variable nodes, declared as private ArrayList<Integer>[] nodes, is an array of length n allocated in the constructor.

Class notes

  • For each node v, nodes[v] contains all nodes that are adjacent to v.
  • The constructor initializes the array and creates an empty ArrayList<Integer> for each node.
  • The graph is undirected, so when an edge is added between vertices u and v, both adjacency lists must be updated. The code for addEdge is given below.
  • You may assume nodes are numbered from 0 to n–1.
  • The array and lists have already been declared and allocated in the constructor.

Task

You have to complete the boolean hasEdge(int fromNode, int toNode) that is part of the class GraphAdjList. This method returns true if there is an edge from fromNode to toNode.

Reference

  • The documentation for the ArrayList class is available online.
  • The documentation for the GraphADT interface is available online.

  • A partial definition of GraphAdjList is included below for reference.

    public class GraphAdjList extends GraphADT<Integer>
{
private ArrayList<Integer> nodes[];

// creates nodes array and the lists
public GraphAdjList(int n) {}

// Adds a new edge for undirected graph,
// so we put the edge in both nodes...
public void addEdge(int fromNode, int toNode)
{
    // some error checking is not shown for clarity
    nodes[fromNode].add(toNode);
    nodes[toNode].add(fromNode);
}

public boolean hasEdge(int fromNode, int toNode)
{ } // to be implemented 

// other details not shown
}

Your Answer:

Reset
Next exercise

Feedback

Your feedback will appear here when you check your answer.