// File: Graph.java

// Author: Rita Ester

// Team: (your names here)

// Date: Mar. 24, 2018.

// Description: Graph class for CSCI 225 lab07

//

import java.util.LinkedList;

// can be used to create the Adjacency list for the Graph representation,

// and to create the queue and the stack needed.

public class Graph {

// This class represents a directed graph using

// an adjacency list representation

private int nbVertices; // No. of vertices

private LinkedList adjList[]; //Adjacency Lists

// Constructor

public Graph(int v){

nbVertices = v;

adjList = new LinkedList[nbVertices];

for (int i=0; i

adjList[i] = new LinkedList();

}

// Method to add an edge to the graph

public void addEdge(int v1, int v2){

adjList[v1].add(v2);

}

// prints the adjacency lists of the graph.

public void printAdjacencyLists(){

for (int i=0; i

System.out.print(" Neighbors at node "+i + ": ");

for (int j=0; j

System.out.print(adjList[i].get(j) +" - ");

}

System.out.println();

}

// prints the vertices (separated by comma) of a BFS traversal starting at vertex

// Author:

public void BFS(int vertex){

// to be completed

}

// DFS prints the vertices (separated by comma) of a DFS traversal starting at vertex.

// Author:

public void DFS(int vertex){

// to be completed

}

}

----------------------------------------------------------------------------------------------------------------------------------

// File: Lab07Driver.java

// Author: Rita Ester

// Team: (your names here)

// Date: Mar. 24, 2018

// Description: Driver file for CSCI 225 Lab 07 (Graphs)

public class Lab07Driver {

public static void main(String[] args) {

Test1();

Test2();

Test3();

// add your own tests here.

// TestA() by Author:

// TestB() by Author:

}

public static void Test1(){

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

System.out.print("***** Test 1 Graph");

g.printAdjacencyLists();

System.out.print(" BFS starting at vertex 2: ");

g.BFS(2);

System.out.print(" DFS starting at vertex 2: ");

g.DFS(2);

System.out.println();

}

public static void Test2(){

Graph g = new Graph(8);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(0, 3);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 5);

g.addEdge(2, 6);

g.addEdge(3, 1);

g.addEdge(3, 7);

g.addEdge(4, 2);

g.addEdge(5, 1);

g.addEdge(5, 3);

g.addEdge(6, 4);

g.addEdge(6, 5);

g.addEdge(7, 6);

System.out.print(" ***** Test 2 Graph");

g.printAdjacencyLists();

System.out.print(" BFS starting at vertex 6: ");

g.BFS(6);

System.out.print(" DFS starting at vertex 6: ");

g.DFS(6);

System.out.println();

}

public static void Test3(){

Graph g = new Graph(9);

g.addEdge(0, 1);

g.addEdge(0, 4);

g.addEdge(0, 7);

g.addEdge(1, 0);

g.addEdge(1, 2);

g.addEdge(1, 4);

g.addEdge(2, 1);

g.addEdge(2, 6);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(4, 5);

g.addEdge(5, 4);

g.addEdge(5, 8);

g.addEdge(6, 2);

g.addEdge(7, 0);

g.addEdge(8, 5);

System.out.print("**** Test 3 Graph");

g.printAdjacencyLists();

System.out.print(" BFS starting at vertex 0: ");

g.BFS(0);

System.out.print(" DFS starting at vertex 0: ");

g.DFS(0);

System.out.println();

}

}

In this lab exercise, you are to implement the BFS and the DFS methods of a Graph class. The partially-completed class Graph.java file can be downloaded from the course website. The BFS and the DFS methods were demonstrated in class; refer to the lecture notes for your implementation. Use Lab07Driver.java to test your implementations. Add at least two more test cases. The Graph class uses an adjacency list representation for the graph and assumes that each node has its unique integer number. It uses the LinkedList class of the Java API to implement the adjacency lists. The get(index) method helps to retrieve the element at index from a 0-indexed list. Check out the constructor, the addEdge and the printAdjacencyList methods to get familiar with the use of the LinkedList class. BFS(int vertex) This method will print out the numbers of the vertices of a BFS traversal starting at vertex. A LinkedList object queue with the methods offer (for enqueue) and poll (for dequeue) should be used to manage the vertices when traversing the graph. Find details on the methods in the ava DFS(int vertex) This method will print out the numbers of the vertices of a DFS traversal starting at vertex. A LinkedList object stack with the methods push, pop, and peekFirst (for peek) should be used to manage the vertices when traversing the graph. Find details on the methods in the ava This lab should to be completed in teams of two. Each team member should implement one of the methods and . add one new test case together with the expected outputs for BFS and for DFS (in the comment above the test) Write your team members' names in the comments at the top of each file, and mark clearly who implemented which method and who added which test case Help each other and discuss your solutions