I am creating a program that forms BFS and DFS upon a user inputted matrix. However, there is two errors in my code I am having trouble figuring out how to fix.
My BFS and DFS both are trying to create an array that takes a constant value in the form of a variable from a constructor. I know it is a scope issue, but what should I do instead?
My second question is; my dequeue and pop functions for my queue class and stack class are supposed to take a char as a parameter, but in my BFS and DFS functions, I am unsure what I should put in as that. How should I rewrite my dequeue and pop functions or what should I put in as the parameter?
//Here is my driver.cpp
// Description: This program performs BFS and DFS on a user inputted matrix.
#include <iostream>
#include "Stack.h"
#include "Queue.h"
using namespace std;
const int MAX_SIZE = 100;
class Graph { //Graph class containing BFS and DFS
private:
int size;
public:
int adjMatrix[MAX_SIZE][MAX_SIZE];
Graph(int n) : size(n) { //Graph constructor
// Initialize adjacency matrix
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
adjMatrix[i][j] = 0;
}
}
}
void addEdge(int i, int j) { //Add Edge function
adjMatrix[i][j] = 1;
adjMatrix[j][i] = 1; // Assuming an undirected graph
}
void DFS(int start) { //Depth First Search Function
bool visited[size] = { false };
Stack stk;
stk.push(start);
while (!stk.isEmpty()) {
int vertex = stk.top();
stk.pop();
if (!visited[vertex]) {
cout << "From " << start + 1 << " to " << vertex + 1 << endl;
visited[vertex] = true;
for (int i = 0; i < size; ++i) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
stk.push(i);
}
}
}
}
}
void BFS(int start) { //Breadth First Search function
bool visited[size] = { false };
Queue q;
q.enqueue(start);
while (!q.isEmpty()) {
int vertex = q.front();
q.dequeue();
if (!visited[vertex]) {
cout << "From " << start + 1 << " to " << vertex + 1 << endl;
visited[vertex] = true;
for (int i = 0; i < size; ++i) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
q.enqueue(i);
}
}
}
}
}
};
int main() { //Main function
int size;
cout << "What is the size of the graph: "; //Ask user for size of graph
cin >> size;
Graph graph(size);
cout << "Enter the adjacency matrix:" << endl; //Ask user to input the matrix according to the inputted size of graph
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
cin >> graph.adjMatrix[i][j];
}
}
int start;
cout << "What is the starting vertex: "; //Ask user for the starting vertex
cin >> start;
start--;
cout << "nDFS" << endl; //Start DFS
graph.DFS(start);
cout << "nBFS" << endl; //Start BFS
graph.BFS(start);
return 0;
}
//Here is my Stack.h
#pragma once
#include <iostream>
using namespace std;
class FullStack
// Exception class thrown by Push when stack is full.
{};
class EmptyStack
// Exception class thrown by Pop and Top when stack is emtpy.
{};
struct NodeType {
char value;
NodeType* next;
};
class Stack
{
private:
NodeType* topPtr;
public:
Stack();
// ~Stack();
void push(char x);
void pop(char& x);
char top();
bool isEmpty();
bool isFull();
};
char Stack::top()
{
if (isEmpty())
throw EmptyStack();
else
return topPtr->value;
}
Stack::Stack() // Class constructor.
{
topPtr = NULL;
}
bool Stack::isEmpty()
{
return (topPtr == NULL);
}
bool Stack::isFull()
{
NodeType* nodePtr;
try {
nodePtr = new NodeType;
delete nodePtr;
return false;
}
catch (std::bad_alloc exception) {
//return true;
throw FullStack();
}
}
void Stack::pop(char& x)
{
if (isEmpty())
throw EmptyStack();
x = topPtr->value;
NodeType* temp = topPtr;
topPtr = topPtr->next;
delete temp;
}
void Stack::push(char x)
{
if (isFull())
throw FullStack();
NodeType* nodePtr = new NodeType();
nodePtr->value = x;
nodePtr->next = topPtr;
topPtr = nodePtr;
}
//Here is my Queue.h
#pragma once
#include <iostream>
using namespace std;
class EmptyQueue
// Exception class thrown by Pop and Top when stack is emtpy.
{};
struct QueueNodeType {
char value;
QueueNodeType* next;
};
class Queue {
private:
QueueNodeType* qFront;
QueueNodeType* qRear;
public:
Queue();
bool isEmpty();
bool isFull();
char front();
void enqueue(char);
void dequeue(char& x);
};
Queue::Queue()
{
qFront = qRear = NULL;
}
char Queue::front()
{
if (isEmpty())
throw EmptyQueue();
else
return qFront->value;
}
bool Queue::isEmpty()
{
if (qFront == NULL)
return true;
else
return false;
}
bool Queue::isFull()
{
QueueNodeType* ptr = new QueueNodeType;
if (ptr == NULL)
return true;
else {
delete ptr;
return false;
}
}
void Queue::enqueue(char x)
{
if (isFull()) exit(1);
QueueNodeType* newNode = new QueueNodeType;
newNode->value = x;
newNode->next = NULL;
if (qFront == NULL)
qFront = newNode;
else
qRear->next = newNode;
qRear = newNode;
}
void Queue::dequeue(char& x)
{
if (isEmpty())
exit(1);
x = qFront->value;
QueueNodeType* temp = qFront;
qFront = qFront->next;
delete temp;
}
user23806214 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.