Project5a: Build a Graph Class

In this part of the project you are to construct a Graph Class that we will use and add methods to as we study graphs.  You will build the class using a Adjacency List structure. Although you can construct one using linked lists we will simplify it considerably using vectors.  More specifically a vector< vector< pair<int,int> > > .  The pair here is used to store a node# with the weight, assuming we have a weighted graph.  Use the following .h file to start off the Graph.  Write the initial two methods DFS and BFS returning the relevant tree in both cases.  Test this with some small graphs that you can generate  here.  As we do on the UVa site read from redirected data.dat to build your graph.  The format of this file is as follows. The first line contains a string and an integer with the former being U or D (directed or undirected) and the integer indicating the number N of vertices in the graph ( 0…N-1).  Then the remainder of the file is a collection of edges, one edge per line.  Your program is to print out the BFS(5) on one line and the DFS(-1) on the subsequent line.  Turn in your project on a Jumpdrive with the source printout within a folder.  A data file of my own choosing will be run thru your program.

Example file data.dat

U 6
0 2
0 4
0 5
1 4
1 5
2 3
2 4
4 5

Using the above data BFS(5) generates  parent vector  5 5 0 2 5 -1 and DFS(-1) generates  parent vector -1 4 0 2 2 1

Reminder: Document as I have requested, as you write the code, not later.

#include <vector>
using namespace std;
enum dtype { DIRECTED, UNDIRECTED };
enum color {WHITE,BLACK,GREY};
class Graph
   // The wt value will be used in a later algorithm.
   vector<vector<pair<int,int>>> G; //Pair < node#, wt >
   vector<color> Color;// Not really required but will reduce parameter passing.
   dtype dir;
   void DFS_Visit(int,vector<int>&);
   Graph(int,dtype); // resizes G to int and sets dir to type.
   // NOTE: AddEdge loads both edges if dir = UNDIRECTED
   void AddEdge(int from, int to, int wt);
   vector<int> BFS(int);// return the parent vector (ie the BFS tree for this vertex)
   vector<int> DFS(int);// Note: if the parameter is a vertex do a single DFS // on this vertex. If the parameter is -1 do the complete // DFS returning a forest of trees. };

Comments are closed.