Lab 7: Graphs (100 pts)
Due Saturday, November 7 at midnight on Catalyst
Part 1: Tutorial on Vectors
 Although you have not studied vectors in the past, they are a commonlyused part of the C++ language.
 I would like you to learn how to use them before you leave 22C.
 Also, they will be very useful in our Graph data structure, as we will create a vector of linked lists to represent our Graph. (Think adjacency list representation of the graph).
 Therefore, it is time to learn about vectors if you never have before.
 Don't worry! Vectors are easy  actually easier to use than arrays, as there are many things that vectors do for you.
 To start, look over the vector tutorial here.
 If you would like further explanation, you can watch this video here.
Part 2: Graph Implementation  Copy the code below into a new header file called Graph.h
 Then, create a new source code file called Graph.cpp.
 Since we are not using templates, we are going to write our function definitions inside of the Graph.cpp.
 We will test them in GraphTest.cpp
 We will be using the adjacency list representation of a Graph for this data structure.
 The heart of the Graph data structure will be a vector of linked lists, to store the adjacent vertices of each vertex in the Graph:
Image source.
 For this assignment, you could visualize the above Graph as shown in the diagram to its right.
 1, 2, 3, 4 and 5 in the left hand column of the diagram are indices of the vector (array).
 Those values to their right are their adjacency lists which are stored as linked lists.
 Specifically, for our purposes, we will be representing the Graph as a vector of linked lists named "adj"
 Thus, we could visualize storing the graph as depicted below for this assignment:
adj[0] (purposely left empty!) adj[1] = 2 > 3 > 4 > NULL //at index 1, we store the adjacency list of vertex 1 adj[2] = 3 > NULL //at index 2, we store the adjacency list of vertex 2 adj[3] = 2 >NULL //at index 3, we store the adjacency list of vertex 3, etc
Header File #include <iostream> #include <cstdlib> #include "List.h" #include <vector>using namespace std;
class Graph {
public:
/**Constructors and destructors*/
Graph(int n); //initializes an empty graph to have n vertices
~Graph();
/*** Access functions ***/
int getNumEdges();
int getNumVertices();
/*** Manipulation procedures ***/
void addEdge(int u, int v);
//inserts vertex v into the adjacency list of vertex u (i.e. inserts v into the list at index u)
/*** Other operations ***/
void printGraph(); //prints as the adjacency list representation of the graph //see below private: int vertices, edges; //number of edges and vertices vector<List<int> > adj; // we will use a vector here for our array
//This vector is the heart of the graph as it stores the adjacency lists of the graph
};
Graph Constructor Help  Inside of your Graph.cpp, start by writing the default constructor for a new Graph.
 The purpose of the constructor is to create an empty List at each vector index (as well as initialize the vertices and edges fields).
 In other words, first, we will want to create a new, empty List to represent one index of the vector.
 Then, we will push this new List onto the back of our vector. (Hint: which vector function will you use here?)
 This process should repeat for all indices of your vector (i.e. for all the vertices in the graph).
 What type of loop do you want here and when will it start and stop? Hint: Do you know the number of vertices in the Graph?
 For ease of implementation: I strong recommend using indices 1 up through and including the number of vertices, and leaving index 0 blank.
 When you are finished writing the constructor, open up a new C++ file called GraphTest.cpp.
 Add a main function inside of GraphTest.cpp and instantiate a new Graph.
 Once your code compiles and runs, work next on addEdge and then on printGraph.
A Word on Printing
 We are representing our Graph using the Adjacency List Representation.
 Thus, we will need to print out its adjacency lists.
 Below is an example of how to print your Graph.
1: 2, 5 2: 1, 3, 4 3: 4 4: 5: 1, 4, 5
 I strongly recommend that you alter your List print function for this assignment so that it prints comma separated values as shown above.
What to Submit
 Once you are certain all of your functions are working, upload your files to Catalyst under Lab 7
 Submit your complete Graph, including List.h, Graph.h, Graph.cpp, and GraphTest.cpp
 Note that you will lose 15 points per function for any missing function
 You will lose 15 points for not testing your functions inside of GraphTest.cpp
