## Instructions

**Objective**

Write a C++ assignment 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.- 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):- Single space between digits.
- 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.- 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 <iostream.h>

#include <fstream.h>

#include <cstdlib.h>

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;

}

## Related Samples

Explore our sample C++ assignments to witness our proficiency in tackling complex coding challenges. Each example showcases efficient, well-documented solutions, reflecting our expertise in C++ programming. Count on us for expert guidance and exceptional assignment solutions, ensuring your academic success and mastery of C++ concepts.

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++