Java program using data structures

Use the example Graph code given at the bottom of the instructions for this assignment.

For this assignment we are going to create a map of a city subway system using a Graph data structure. Picture is provided below.

Enter all the information from the Metro Station Map into your Graph following these guidelines:

1) Delete all the vertices and edges that were made in the main method of the example code (start with a blank Graph)

2) Add the network of stations and the travel times (weights) to the graph. Modify the addEdge() method to make the graph undirected (when you add an edge, also add the reverse connection)

3) Using the data in your graph, determine the travel time from station 6 to station 2 when taking the following path: 6,3,1,2

For part 3, DO NOT just sum up the travel times from the Map that was provided. Your code should use the graph you created and follow the path from station to station and sum up the travel times.

import java.util.*;

class Graph

{

// Edge object that is stored for each connection to another node

class Edge

{

int v,w;

public Edge(int v,int w)

{

this.v=v; this.w=w;

}

@Override

public String toString()

{

return "("+v+","+w+")";

}

}

// An array of lists of Edge objects

List G[];

// Parameterized constructor

public Graph(int n)

{

G = new LinkedList[n];

// For each node in the graph, initialize an empty adjacency list

for(int i=0; i

G[i]=new LinkedList();

}

// Check if node U is connected to node V

boolean isConnected(int u,int v)

{

// Check each edge for this node to see if it connects to node V

for(Edge i: G[u])

if(i.v==v) return true;

return false;

}

// For node U, add a new connection to node V, with weight W

void addEdge(int u,int v,int w)

{

G[u].add(new Edge(v,w));

}

// Override the java default toString() method so we can print

// our Graph in the format we want

@Override

public String toString()

{

String result="";

for(int i=0;i

result+=i+"=>"+G[i]+" ";

return result;

}

}

public class GraphExample {

public static void main(String[] args)

{

Graph g=new Graph(10);

g.addEdge(0, 2, 10);

g.addEdge(0, 5, 15);

g.addEdge(2, 5, 10);

g.addEdge(9, 3, 16);

System.out.println(g);

System.out.println(g.isConnected(9,3));

}

}

- Metro Station Map with Travel Time in Minutes. 2 6 26 5 13 28 19 38 3 35 1 27 4