Graph.java

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.StringTokenizer;

/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

public class Graph {

public int V;

public int E;

public LinkedList[] adj;

public Graph()

{

V = 0;

E = 0;

}

public Graph(BufferedReader reader) throws IOException

{

String line;

line = reader.readLine();

V = Integer.parseInt(line);

line = reader.readLine();

E = Integer.parseInt(line);

adj = new LinkedList[V];

for (int v = 0; v

adj[v] = new LinkedList();

}

while ((line = reader.readLine()) != null) {

int tempV1, tempV2;

StringTokenizer st = new StringTokenizer(line, " ");

tempV1 = Integer.parseInt(st.nextToken());

tempV2 = Integer.parseInt(st.nextToken());

addEdge(tempV1, tempV2);

}

}

public void addEdge(int v, int w) {

}

public String tostring()

{

String s = new String();

s = "There are "+V+" vertices and "+E+" edges ";

for(int i=0;i

{

s = s+i+": ";

for(int j = 0; j

{

s = s+adj[i].get(j)+" ";

}

s = s+" ";

}

return s;

}

}

The Graph class has been uploaded in Canvas. It implements adjacency lists to store the neighbors of a vertex. Extend the graph class to make two nevw subclasses DirectedGraph and UndirectedGraph. Hint: Override the addEdge( method Write a driver program, which reads input files mediumG.txt as an undirected graph and reads an input file tinyDG.txt as a directed graph. This driver program should display the graphs in the form of adjacency lists. Implement BFS algorithm on an undirected graph following the pseudo-code given below. Read the file mediumG.txt as the input graph. Print the BFS paths from a source to all the other nodes in the graph