×
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
Understand Haskell’s core concepts like pure functions, recursion, and immutability before diving into assignments. Use type annotations to catch errors early and test small components frequently. Tools like GHCi can help you experiment and debug interactively—perfect for refining functional logic.
News
In Spring 2025, IntelliJ IDEA 2025.2 EAP launched, bringing enhanced remote development, Spring ecosystem updates, Maven 4 support, and UI/HTTP client improvements—perfect for students working on cloud-based Java or Kotlin assignments

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.