Lab Task $03$:

Complete the Graph.java method: private boolean isReachable$($int src$,$ int dest, boolean$[]$ visited$)$ in the

folder Task $03$ such that it returns true if the destination vertex dest is reachable from the source vertex src;

otherwise, it returns false.

Complete the test program to prompt for and read the source and destination vertices. It then checks whether the

destination vertex is reachable from the source vertex. $[$Note: Assume that the values read are valid.$]$

import java.util.List;

import java.util.ArrayList;

import java.util.Queue;

import java.util.ArrayDeque;

$//$ Determines if a vertex is reachable from another vertex in a directed graph

public class Graph $\{$

private List$>$ adjList $=$ null;

private int numVertices;

public Graph$($List edges, int numVertices$)\{$

this.numVertices $=$ numVertices;

adjList $=$ new ArrayList;

for $($int i $=0$; i $$ numVertices; i$++)\{$

adjList.add$($new ArrayList;

$\}$

$//$ add edges to the directed graph

for $($Edge edge: edges$)\{$

int src $=$ edge.source;

int dest $=$ edge.dest;

adjList.get$($src$).$add$($dest$)$;

$\}$

$\}$

public boolean isReachable$($int src$,$ int dest$)\{$

boolean$[]$ visited $=$ new boolean$[$numVertices$]$;

return isReachable$($src$,$ dest, visited$)$;

$\}$

$//$ Function to perform BFS traversal from the source vertex in the graph to

$//$ determine if the destination vertex is reachable from the source or not

private boolean isReachable$($int src$,$ int dest, boolean$[]$ visited$)$

$\{$

$//$ to be completed by students

$\}$

$\}$

public class Edge$\{$

public int source, dest;

private Edge$($int source, int dest$)\{$

this.source $=$ source;

this.dest $=$ dest;

$\}$

public static Edge getEdge$($int a$,$ int b$)\{$

return new Edge$($a$,$ b$)$; $//$ calls private constructor

$\}$

$\}$

import java.util.List;

import java.util.Arrays;

import java.util.Scanner;

public class GraphDriver$\{$

public static void main$($String$[]$ args$)\{$

Scanner scanner $=$ new Scanner$($System$.$in$)$;

List edges $=$ Arrays.asList$($Edge$.$getEdge$(0,3),$ Edge.getEdge$(1,0),$

Edge.getEdge$(1,2),$ Edge.getEdge$(1,4),$

Edge.getEdge$(2,7),$ Edge.getEdge$(3,4),$

Edge.getEdge$(3,5),$ Edge.getEdge$(4,3),$

Edge.getEdge$(4,6),$ Edge.getEdge$(5,6),$

Edge.getEdge$(6,7))$;

$//$ Number of nodes in the graph $($labelled from $0$ to N$-1)$

int numVertices $=8$;

$//$ To be completed by students

$\}$

$\}$