CSCI 362 — Lab 8

Graph Algorithms

Due: July 12, 2019 @ 11:59PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab8-graph-algorithms.tar

Overview

This lab is not autograded. You are tasked with updating two files: GraphAlgorithms.cpp and Driver.cpp

Required Functions (70 points)

Instead of implementing all of the graph algorithms we discussed in class, you get to choose a subset:

NOTE: you may find kruskals and bellman_ford to be easier to implement.

namespace GraphUtils
{

// traversal algorithms [30pts]
// -----------------------------------------------------------------------------
// each method returns a vector of vertices indicating the order

// One of:
std::vector<size_t>
bfs (Graph const& g, size_t start);
// OR
std::vector<size_t>
dfs (Graph const& g, size_t start);

// And also implement
std::vector<size_t>
topological_sort (Graph const& g);


// minimum spanning tree algorithms [20pts]
// -----------------------------------------------------------------------------
// each method returns a vector of Edges indicating the Edges that form
// a minimum spanning tree

// One of:
EdgeList
prims (Graph const& g, size_t start);
// OR
EdgeList
kruskals (Graph const& g);


// shortest path algorithms [20pts]
// -----------------------------------------------------------------------------
// - edges returns should be constructed (made) from the "prev"
//   vertex, the current vertex, and the "dist" weight calculated
// - remember to initialize all "dist" to std::numeric_limits<double>::max()
// (Dijkstra only)
// - Create an unordered_set to keep track of logically removed vertices


// One of:
EdgeList
dijkstra (Graph const& g, size_t start);
// OR
EdgeList
bellman_ford (Graph const& g, size_t start);

} // end namespace GraphUtils

Driver Application (30 points)

The driver should construct a unique graph for each algorithm and output the results. Consult the example starter code I provide.

Style

Use good programming style:

Submission

Since this consists of multiple files, a tarball will be required for submission.

invoking make handin should create handin.tar

Please submit handin.tar to autolab

Grading

This lab is graded out of 100 points.