Sale!

Assignment 9 – Graphs

$30.00

CSCI 2270 – Data Structures – Section 100

Assignment 9 – Graphs
OBJECTIVES
1. Build an undirected weighted graph
2. Perform Breadth First Traversal (BFT) and Depth First Traversal (DFT)
Overview
You were just a humble map programmer, but that was before the zombies attacked! Now, your
skills are put to coordinating the survivors and finding routes between cities that haven’t been
overtaken. Some of the roads between these cities have been overrun and you will have to
avoid them, which has caused the nation to be divided into multiple smaller districts (think
disconnected components in a graph). You will have to build a graph with each vertex
representing a city and each edge between vertices representing a route between them. The
following structs will facilitate your graph.

Category:
5/5 - (2 votes)

CSCI 2270 – Data Structures – Section 100

Assignment 9 – Graphs
OBJECTIVES
1. Build an undirected weighted graph
2. Perform Breadth First Traversal (BFT) and Depth First Traversal (DFT)
Overview
You were just a humble map programmer, but that was before the zombies attacked! Now, your
skills are put to coordinating the survivors and finding routes between cities that haven’t been
overtaken. Some of the roads between these cities have been overrun and you will have to
avoid them, which has caused the nation to be divided into multiple smaller districts (think
disconnected components in a graph). You will have to build a graph with each vertex
representing a city and each edge between vertices representing a route between them. The
following structs will facilitate your graph.
/* structure for edge connecting an adjacent vertex */
struct Edge
{
vertex *v;
int distance;
};
/* structure for each vertex in the graph */
struct vertex
{
std::string name;
bool visited;
std::vector<Edge> Edges; // stores edges to adjacent vertices
};
You will store the graph as a vector of vertex structs, where each city contains an adjacency list
stored as a vector of Edge structs. This data structure is described in Graph.hpp and can be
represented like this:
CSCI 2270 – Data Structures – Section 100
Instructor: Shayon Gupta, Ashutosh Trivedi, Maciej Zagrodzki
Which would represent the following graph:
Graph Class
There is no need to manage dynamic memory in this assignment so you may leave your
constructor/destructor empty.
void addVertex(std::string cityName)
➔ Create a new vertex with name cityName and push it back to your vector of vertices.
void addEdge(std::string city1, std::string city2, int distance)
CSCI 2270 – Data Structures – Section 100
Instructor: Shayon Gupta, Ashutosh Trivedi, Maciej Zagrodzki
➔ Establish a single edge from city1 to city2. Create an edge with distance equal to
distance and v equal to the address of the vertex with name city2. Then push back the
edge to the Edges vector of the vertex with name city1.
void displayEdges()
➔ For each vertex in your vertices vector, print the city name and each city with which it is
connected along with the distance in miles between them using the following example
format. The graph below has three vertices that are all connected.
// Boulder has an edge to Denver with distance 2 and an
// edge to Chicago with distance 15
Boulder–>Denver (2 miles)***Chicago (15 miles)
Chicago–>Boulder (15 miles)***Denver (10 miles)
Denver–>Boulder (2 miles)***Chicago (10 miles)
void printDFT()
➔ Use a depth first traversal of the graph to print the names of every city beginning with the
first vertex in your vertices vector. Use your helper functions setAllVerticesUnvisited
and DFT_traversal. Note that there may be disconnected components in the graph!
void printBFT()
➔ Same as above with a breadth first traversal instead.
void setAllVerticesUnvisited()
➔ Loop through your vertices vector and set each vertex’s visited field to false. This
function should be called right before any traversal (BFT, DFT) that uses the visited
member.
vertex *findVertex(std::string name)
➔ Return a pointer to the vertex with the specified name.
void BFT_traversal(vertex *v)
➔ Perform a breadth first traversal of the graph beginning with vertex v, printing the name
of each vertex you visit.
cout << v->name << endl;
void DFT_traversal(vertex *v)
➔ Same as above with depth first traversal instead.
CSCI 2270 – Data Structures – Section 100
Instructor: Shayon Gupta, Ashutosh Trivedi, Maciej Zagrodzki
Driver
Unlike previous assignments, your program will not have a menu. Instead, it should begin by
reading data out of a file, where the name of this file is passed as a command line argument.
An example file can be found on Moodle with the name simpleCities.txt. This file is in the
following format
cities,Boulder,Denver,Chicago,Boston,Austin
Boulder,0,2,15,-1,-1
Denver,2,0,10,-1,8
Chicago,15,10,0,5,-1
Boston,-1,-1,5,0,-1
Austin,-1,8,-1,-1,0
The first row and first column contain the name of each city in the graph. The rest of the values
correspond to the distance between those cities
● A positive value represents the distance(in miles) between the row and the column city
● While the value -1 indicates that there is no path connecting the two cities.
Every time you read in a new edge with a distance greater than 0, use the following print
statement:
cout << ” … Reading in ” << city << ” — ” << connectedCity << ” — ” <<
distance << endl;
After your graph is built, demonstrate your different traversal methods with the following lines of
code:
cout << “—————————— ” << endl
<< “Breadth First Traversal” << endl
<< “——————————” << endl;
g.printBFT();
cout << “—————————— ” << endl
<< “Depth First Traversal” << endl
<< “——————————“<< endl;
g.printDFT();
cout << “—————————— ” << endl
<< “Display Edges” << endl
<< “——————————“<< endl;
CSCI 2270 – Data Structures – Section 100
Instructor: Shayon Gupta, Ashutosh Trivedi, Maciej Zagrodzki
g.displayEdges();

Open chat
Need help?
Hello
Can we help you?