CodeWorkout
  1. Home
  2. Gym
  3. Practice In-Class Quiz 4
  4. X1599: Write method hasPathBFS

X1599: Write method hasPathBFS

Description

You are given an undirected graph representing rooms in a building and the doors connecting them. A security robot starts in a given room source. The robot wants to determine whether it can reach a specific target room target by moving through doors.

Write a method boolean hasPathBFS(Graph g, int source, int target) that returns true if there is a path from source to target using the graph represented by g. This method should use a Breadth-First Search (BFS) to determine whether a path exists from room source to target. The BFS code is given below.

The code given starts at source and traverses the graph using the BFS logic until it has completed the traversal. Your modification should return true if it reaches target.

The graph is represented with an object of type Graph which implements the GraphADT interface (partially shown below).

Reference

The documentation for GraphADT is available online, and we have included a partial definition of Graph here for convenience.

public class Graph implements GraphADT<String> ...
{
    // Is this graph a directed graph?
    public boolean isDirected();

    // Return the number of nodes in this graph
    public int getNodeCount();

    // Return the number of edges in the graph.
    public int getEdgeCount();

    // Returns true iff the graph has the edge
    // from v to w.
    public boolean hasEdge(int v, int w);

    // Return the number of edges on node v.
    public int getNodeDegree(int v);
}

Your Answer:

Reset
Next exercise

Feedback

Your feedback will appear here when you check your answer.