Graph.java import java.io.BufferedReader; import java.io.File; import java.io.Fi

Question

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<Integer>[] 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 < V; v++) {

adj[v] = new LinkedList<Integer>();

}

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<V;i++)

{

s = s+i+": ";

for(int j = 0; j<adj[i].size();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.

Explanation / Answer

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<Integer>[] 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 < V; v++) {

adj[v] = new LinkedList<Integer>();

}

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) {

adj[v].add(w);

}

   void BFS(int s)
    {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];

        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);

        while (queue.size() != 0)
        {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

public String tostring()

{

String s = new String();

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

for(int i=0;i<V;i++)

{

s = s+i+": ";

for(int j = 0; j<adj[i].size();j++)

{

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

}

s = s+" ";

  

}

return s;

}

  

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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