×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

C++ Program to Model an Undirected Graph Assignment Solution

June 28, 2024
Len E. Villasenor
Len E.
🇺🇸 United States
C++
Len E. Villasenor, with a master’s in computer science from Northern Arizona University, boasts 5 years of expertise in C++ assignment assistance, providing exceptional guidance in this specialized area.
Key Topics
  • Instructions
  • Requirements and Specifications
    • Implement the following public member functions.
Tip of the day
Use the REPL (Read-Eval-Print Loop) to test your code interactively, and practice writing concise, readable expressions to harness Scala’s powerful syntax effectively.
News
In 2024, JavaScript's Redux saw updates for efficient state management, and Tailwind CSS gained traction for responsive design. Meanwhile, C++ libraries like Boost.

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.
    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

program to model undirected graph in C

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.