# C++ Program to Model an Undirected Graph Assignment Solution.

## Instructions

Objective

Write a C++ class definition for an abstract data type called Graph that models an undirected graph.

## Requirements and Specifications

### Implement the following public member functions.

• Graph(char *fileName): A constructor that creates the graph using the file passed into the function.
1. The format of the file is described later in the document
• Graph(): An appropriate destructor.
• void display() const: Displays the graph's adjacency matrix to the screen using this format (see examples later):
1. Single space between digits.
2. First row (top) and first column (left) is vertex 0, second row and column is vertex 1,…, last row (bottom) and last column (right) is vertex n – 1.
• void displayDFS(int vertex) const: Displays the result of a depth first search starting at the provided vertex.
1. When you have a choice between selecting two vertices, pick the vertex with the lower number .
• bool isBipartite() const: Returns true if the graph is bipartite and false otherwise.

Screenshots of output

Source Code

```// NAME: // FILE: Graph.cpp // DESCRIPTION: Implementation of the Graph class. #include  #include #include using namespace std; #include "Graph.h" #include "QueueInt.h" #include "StackInt.h" // Constructor: load the graph from a file Graph::Graph(char *filename) { string line; ifstream graphFile(filename); graphFile >> this->numVertices; this->createMatrix(this->numVertices); int vertexA; int vertexB; int weight; while (graphFile >> vertexA) { graphFile >> vertexB; graphFile >> weight; this->addEdge(vertexA, vertexB, weight); } graphFile.close();  }  // Destructor Graph::~Graph() { for (int i = 0; i < this->numVertices; i++) { delete[] this->matrix[i]; } delete[] this->matrix; }  // Display the adjacency matrix void Graph::display() const { for (int i = 0; i < this->numVertices; i++) { for (int j = 0; j < this->numVertices; j++) { if (i == j) { cout << 0; } else if (this->matrix[i][j] == -1) { cout << "x"; } else { cout << this->matrix[i][j]; } cout << " "; if (j == this->numVertices - 1) { cout << endl;       }     }   } } // Displays the depth first search starting at the given vertex void Graph::displayDFS(int vertex) const { cout << " DFS at vertex 0: " << vertex << ": "; bool visited[this->numVertices]; for (int i = 0; i < this->numVertices; i++) { visited[i] = false; } this->dfsHelper(vertex, visited); cout << endl; } void Graph::dfsHelper(int vertex, bool *visited) const { visited[vertex] = true; cout << vertex << " "; for (int i = 0; i < this->numVertices; i++) { if (!(visited[i]) && this->isAdjacent(vertex, i)) { dfsHelper(i, visited);     }   } } // Perform breadth first search starting at the given vertex void Graph::displayBFS(int vertex) const {   cout << "BFS at vertex 0: " << vertex << ": ";   bool visited[this->numVertices];   for (int i = 0; i < this->numVertices; i++)   {     visited[i] = false;   }   QueueInt queue;   visited[vertex] = true;   cout << vertex << " ";   queue.enqueue(vertex);   while (!queue.isEmpty())   {     vertex = queue.dequeue();     for (int i = 0; i < this->numVertices; i++)     {       if (!(visited[i]) && this->isAdjacent(vertex, i))       {         visited[i] = true;         cout << i << " ";         queue.enqueue(i);       }     }   }   cout << endl; } int *Graph::mstNextEdge(bool *visited, int edge[]) const { edge[0] = -1; edge[1] = -1; edge[2] = -1; for (int i = 0; i < this->numVertices; i++) { for (int j = 0; j < this->numVertices; j++) { int weight = this->matrix[i][j]; if (this->isAdjacent(i, j) && (visited[i] && !visited[j])) { if (edge[0] == -1 || edge[1] == -1) { edge[0] = i; edge[1] = j; edge[2] = weight; } int minWeight = this->matrix[edge[0]][edge[1]]; if (weight < minWeight) { edge[0] = i; edge[1] = j; edge[2] = weight;         }       }     }   } return edge; } // Create 2D matrix void Graph::createMatrix(int numVertices) { this->matrix = new int *[numVertices]; for (int i = 0; i < numVertices; i++) { this->matrix[i] = new int[numVertices]; for (int j = 0; j < numVertices; j++) { this->matrix[i][j] = -1;     }   } } void Graph::addEdge(int vertexA, int vertexB, int weight) { this->matrix[vertexA][vertexB] = weight; this->matrix[vertexB][vertexA] = weight; } bool Graph::isAdjacent(int vertexA, int vertexB) const {  return this->matrix[vertexA][vertexB] > 0; } // Determine whether the graph is bipartite or not bool Graph::isBipartite() const { return false; }```