Design a graph class that stores a directed, unweighted graph using an adjacency

Question

Design a graph class that stores a directed, unweighted graph using an adjacency matrix. Vertices
will be contiguous integers starting at 0, and the number of vertices will be available when the graph
is constructed.
Here’s a starting point for your Graph class, illustrating the methods you’ll need to write:
public class Graph {
private boolean[][] adjacency;
// this graph has vertices labeled 0 to numVertices-1
public Graph(int numVertices)
{
}
// store a directed edge from fromVertex to toVertex
public void setEdge(int fromVertex, int toVertex)
{
}
// return a list of connected vertices to get from source to destination
// return null if path does not exist
public List<Integer> shortestPath(int source, int destination)
{
// build up bookkeeping according to unweighted single source shortest
// path algorithm in book
// recover path from source to destination using your bookkeeping
}
}
Tester program
A GraphTester class has been provided. Your Graph class must work with mine.
Bookkeeping
This algorithm, like many graph algorithms, requires a data structure to keep track of its progress.
I suggest something like the following:
class PathData
{
public int distance;
public int prevVertex;
}
// bookkeeping data for each vertex during the single source shortest path
// algorithm
ArrayList<PathData> bookkeeping;

Here is the tester class that goes with it….any help would be appreciated!!!

import java.util.Scanner;

public class GraphTester {

public static void main(String[] args)
{
Scanner input = new Scanner(System.in);

// read numVertices and numEdges from scanner
int numVertices = input.nextInt();
int numEdges = input.nextInt();

// create a new Graph with numVertices vertices
Graph graph = new Graph(numVertices);

// read numEdges pairs of source, destination vertices and store in
// graph data structure
for (int i=0; i<numEdges; i++)
{
int s = input.nextInt();
int d = input.nextInt();

graph.setEdge(s,d);
}

// print shortest path to all vertices from vertex 0
for (int i=0; i<numVertices; i++)
{
System.out.print("Path to vertex " + i + ": ");
List<Integer> path = graph.shortestPath(0, i);

if (path == null)
{
System.out.println("No path");
}
else
{
System.out.println(path);
}
}
}
}

Explanation / Answer

import java.util.*;
class Graph {
   private boolean[][] adjacency;

   // this graph has vertices labeled 0 to numVertices-1
   public Graph(int numVertices)
   {
       adjacency = new boolean[numVertices][numVertices];
       for(boolean[] row: adjacency)
       Arrays.fill(row, Boolean.FALSE);
   }

   // store a directed edge from fromVertex to toVertex
   public void setEdge(int fromVertex, int toVertex)
   {
       adjacency[fromVertex][toVertex] = true;
   }

   / return a list of connected vertices to get from source to destination
   // return null if path does not exist
   public List<Integer> shortestPath(int source, int destination)
   {
       // build up bookkeeping according to unweighted single source shortest
       // path algorithm in book
       // recover path from source to destination using your bookkeeping
   }
}

class PathData
{
   public int distance;
   public int prevVertex;
}

// bookkeeping data for each vertex during the single source shortest path
// algorithm
ArrayList<PathData> bookkeeping;

public class GraphTester {
   public static void main(String[] args)
   {
   Scanner input = new Scanner(System.in);

   // read numVertices and numEdges from scanner
   int numVertices = input.nextInt();
   int numEdges = input.nextInt();

   // create a new Graph with numVertices vertices
   Graph graph = new Graph(numVertices);

   // read numEdges pairs of source, destination vertices and store in
   // graph data structure
       for (int i=0; i<numEdges; i++)
       {
           int s = input.nextInt();
           int d = input.nextInt();
           graph.setEdge(s,d);
       }

   // print shortest path to all vertices from vertex 0
       for (int i=0; i<numVertices; i++)
       {
           System.out.print("Path to vertex " + i + ": ");
           List<Integer> path = graph.shortestPath(0, i);
           if (path == null)
           {
               System.out.println("No path");
           }

           else
           {
               System.out.println(path);
           }
       }
  
   }
}

public List<Integer> shortestPath(int source, int destination) is not completed as the book name from which i have to impliment this algorithm is not mentioned

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.