Lab 10: Graphs Part 2 (100 pts) Due Tuesday, June 20 at 1:20pm on CatalystPart 1: Updated Header File
#include <iostream> #include <cstdlib> #include "List.h" #include <vector> using namespace std; Graph(int n); //initializes an empty graph to have n vertices /*** Access Functions ***/ int getNumEdges(); //returns the number of edges in the graph int getNumVertices(); //returns the number of vertices in the graph bool isEmpty(); //returns whether the graph is empty int getDistance(int v); //Pre: v <= numVertices. Returns the value of the distance[v] int getParent(int v); //Pre: v <= numVertices. Returns the value of the parent[v] int getDistance(int v); //Pre: v <= numVertices. Returns the value of distance[v] char getColor(int v); //Pre: v <= numVertices. Returns the value of color[v] /*** 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) //and inserts u into v. /*** Additional Operations ***/ void printGraph(ostream& output); //Prints the adjacency list of each vertex in the graph, //vertex: <space separated list of adjacent vertices> //Prints to the console or to an output file given the ostream parameter void printBFS(ostream& output); //Prints the current values in the parallel vectors after executing BFS //Prints to the console or to an output file given the ostream parameter //First prints the heading: //v <tab> c <tab> p <tab> d <tab> //Then, prints out this information for each vertex in the graph //Note that this function is intended purely to help you debug your code void BFS(int source); //Performs breath first search on this Graph give a source vertex //pre: at least one vertex must exist //pre: source is a vertex in the graph void printPath(int source, int destination, ostream& output); //Prints the path from the source to the destination vertex //Prints to the console or to an output file given the ostream parameter private: int vertices, edges; //number of edges and vertices vector<List<int> > adj; vector<char> color; vector<int> distance; vector<int> parent; };
private:
adj[1] color[1] distance[1] parent[1] All store information about vertex 1 of the Graph.
Part 2: Implement the BFS Algorithm
BFS(G, s) for all x in V(G) color[x] = white distance[x] = 1 parent[x] = Nil color[s] = grey distance[s] = 0 Enqueue(Q,s) while(Q is not empty) x = front of Q Dequeue(Q,x) for all y in adj[x] if color[y] == white color[y] = grey distance[y] = distance[x] + 1 parent[y] = x Enqueue(Q, y) color[x] = black A Word on Printing
v c p d 1 B 0 0 2 B 1 1 3 B 2 2 4 B 2 2 5 B 1 1
File Input and Output
6 1 2 1 3 2 4 2 5 2 6 3 4 4 5 5 6 0 0 1 5 3 6 2 3 4 4 0 0 Example Output File: 1: 2 3 2: 1 4 5 6 3: 1 4 4: 2 3 5 5: 2 4 6 6: 2 5 The distance from 1 to 5: 2 A shortest path from 1 to 5: 1 2 5 The distance from 3 to 6: 3 A shortest path from 3 to 6: 3 1 2 6 The distance from 2 to 3: 2 A shortest path from 2 to 3: 2 1 3 The distance from 4 to 4: 0 A shortest path from 4 to 4: 4
Input File: 7 1 4 1 5 4 5 2 3 2 6 3 7 6 7 0 0 2 7 3 6 1 7 0 0 Output File: 1: 4 5 2: 3 6 3: 2 7 4: 1 5 5: 1 4 6: 2 7 7: 3 6 The distance from 2 to 7: 2 A shortest path from 2 to 7: 2 3 7 The distance from 3 to 6: 2 A shortest path from 3 to 6: 3 2 6 The distance from 1 to 7: infinite No path from 1 to 7 exists The Print Path Algorithm
Print_Path(Graph, source, destination) if destination == source print source else if parent[destination] == 0 print "No path from " source "to " destination exists else Print_Path(Graph, source, parent[destination]) print destination WriteGraph.cpp
Welcome to WriteGraph! ***Reading from input.txt*** Please enter the name of the output file: output.txt Thank you! Your Graph is now written to output.txt! How You Will Be Graded
What to Submit
