Breadth / Depth First Search causes crash when run on graph for second time

Question

So I have a directed graph which I have added vertices and edges to. The graph represents airports and flights between them. When I run a breadth First or a Depth First search to find a path between two airports I get the correct answer the first time, but when I run it the second time with the exact same airports it cannot find a path and the program crashes with error code -1073741819. I've been trying to figure this out for hours and I'm stumped. I ran the debugger and the problem seems to occur when the BFS algorithm goes into the IsMarked() function of the graph. It can't read the vertices[] array and the debugger says

Here is my graph class

#pragma once
#include "queue.h"
const int NULL_EDGE = 0;

template<class VertexType>
class GraphType
{
public:
    GraphType();            // constructor, default of 50 vertices.
    GraphType(int maxV);    // parameterized constructor, maxV <= 50.
    ~GraphType();           // destructor    

    void MakeEmpty();
    bool IsEmpty() const;
    bool IsFull() const;
    void AddVertex(VertexType);
    void AddEdge(VertexType, VertexType, int);
    int WeightIs(VertexType, VertexType);//             (fromVertex, toVertex).
    void GetToVertices(VertexType, QueType<VertexType>&);   
    void ClearMarks();
    void MarkVertex(VertexType);
    bool IsMarked(VertexType) const;
    void DisplayFlights();


private:
    int numVertices;
    int maxVertices;
    VertexType* vertices;
    int edges[50][50];
    bool* marks; // marks[i] is mark for vertices[i].


};


template<class VertexType>
GraphType<VertexType>::GraphType()
// Post: Arrays of size 50 are dynamically allocated for
//       marks and vertices. numVertices is set to 0;
//       maxVertices is set to 50.
{
    numVertices = 0;
    maxVertices = 50;
    vertices = new VertexType[50];
    marks = new bool[50];
    //ClearMarks();
}

template<class VertexType>
GraphType<VertexType>::GraphType(int maxV)
// Post: Arrays of size maxV are dynamically
// allocated for marks and vertices.
// numVertices is set to 0; maxVertices is set to maxV.
{
    numVertices = 0;
    maxVertices = maxV;
    vertices = new VertexType[maxV];
    marks = new bool[maxV];
    //ClearMarks();
}

template<class VertexType>
GraphType<VertexType>::~GraphType()
// Post: arrays for vertices and marks have been   // deallocated.
{
    delete[] vertices;
    delete[] marks;
}

template<class VertexType>
void GraphType<VertexType>::MakeEmpty()
{
   //not yet coded
}


template<class VertexType>
bool GraphType<VertexType>::IsEmpty() const
{
    return (numVertices == 0);
}

template<class VertexType>
bool GraphType<VertexType>::IsFull() const
{
    return (numVertices == maxVertices);
}

template<class VertexType>
void GraphType<VertexType>::AddVertex(VertexType vertex)
// Post: vertex has been stored in vertices.
//       Corresponding row and column of edges have been
//    set to NULL_EDGE.
//       numVertices has been incremented.
{
    //Not allowed to add duplicate vertex
    bool duplicate = false;
    for (int i = 0; i < numVertices; i++) {
        if (vertices[i] == vertex)
            duplicate = true;
    }

    if (!duplicate) {
        vertices[numVertices] = vertex;
        for (int index = 0; index < numVertices; index++)
        {
            edges[numVertices][index] = NULL_EDGE;
            edges[index][numVertices] = NULL_EDGE;
        }
        numVertices++;
    }
    else {
        cerr << "Cannot add duplicate vertex\n";
    }

}

template<class VertexType>
int IndexIs(VertexType * vertices,VertexType vertex)
    // Post: Function value = index of vertex in vertices.
{
    int index = 0;
    while (!(vertex == vertices[index]))
        index++;
    return index;
}

template<class VertexType>
void GraphType<VertexType>::AddEdge(VertexType fromVertex,VertexType toVertex, int weight)
    // Post: Edge (fromVertex, toVertex) is stored in edges.
{
    /*int row;
    int column;*/
    int row = IndexIs(vertices, fromVertex);
    int col = IndexIs(vertices, toVertex);
    edges[row][col] = weight;
}

template<class VertexType>
int GraphType<VertexType>::WeightIs(VertexType fromVertex,VertexType toVertex)
    // Post: Function value = weight associated with the
    //      edge (fromVertex, toVertex).
{
    /*int row;
    int column;*/
    int row = IndexIs(vertices, fromVertex);
    int col = IndexIs(vertices, toVertex);
    return edges[row][col];
}

template<class VertexType>
void GraphType<VertexType>::GetToVertices(VertexType vertex, QueType<VertexType>& adjvertexQ)
{
    int fromIndex;
    int toIndex;

    fromIndex = IndexIs(vertices, vertex);
    for (toIndex = 0; toIndex < numVertices; toIndex++)
        if (edges[fromIndex][toIndex] != NULL_EDGE)
            adjvertexQ.Enqueue(vertices[toIndex]);
}

template<class VertexType>
void GraphType<VertexType>::ClearMarks()
{
    for (int i = 0; i < maxVertices; i++) {
        marks[i] = false;
    }
}

template<class VertexType>
void GraphType<VertexType>::MarkVertex(VertexType vertex)
{
    for (int i = 0; i < numVertices; i++) {
        if (vertex == vertices[i]) {
            marks[i] = true;
            break;
        }
    }

    /*int index = 0;
    while (!(vertex == vertices[index])) {
        if (vertex == vertices[index]) {
            marks[index] = true;
            index++;
        }

    }*/

}

template<class VertexType>
bool GraphType<VertexType>::IsMarked(VertexType vertex) const
{

    for (int i = 0; i < numVertices; i++) {
        if (vertices[i] == vertex) {
            return marks[i];
        }
    }
}

template<class VertexType>
void GraphType<VertexType>::DisplayFlights()
{
    //foreach vertex
    QueType<VertexType> q;
    VertexType adjVertex;
    int weight;
    for (int i = 0; i < numVertices; i++) {
        GetToVertices(vertices[i], q);
        //get adjacent vertices
        while (!q.IsEmpty()) {
            q.Dequeue(adjVertex);
            weight = WeightIs(vertices[i], adjVertex);
            cout << vertices[i] << " to " << adjVertex << " " << weight << endl;
        }
    }

}

And my Breadth First Search

void BreadthFirstSearch(GraphType<string> graph, string startVertex, string endVertex)
    // Assumes VertexType is a type for which the “==“ and “<<“
    // operators are defined.
{
    QueType<string> queue;
    QueType<string> vertexQ;
    bool found = false;
    string vertex;
    string item;
    graph.ClearMarks();
    queue.Enqueue(startVertex);
    do
    {
        queue.Dequeue(vertex);
        if (vertex == endVertex)
        {
            cout << vertex;
            found = true;
        }
        else
        {
            if (!graph.IsMarked(vertex))
            {
                graph.MarkVertex(vertex);
                cout << vertex << " ";
                graph.GetToVertices(vertex, vertexQ);
                while (!vertexQ.IsEmpty())
                {
                    vertexQ.Dequeue(item);
                    if (!graph.IsMarked(item))
                        queue.Enqueue(item);
                }
            }
        }
    } while (!queue.IsEmpty() && !found);
    if (!found)
        cout << "Path not found." << endl;
}

Would really appreciate any help. Thank you very much.

Answer 1

In void BreadthFirstSearch(GraphType<string> graph, string startVertex, string endVertex) you pass GraphType<string> by value, meaning, a temporary copy is created. There the pointers vertices and marks are copied too, but not the values they are pointing to.

So the original and temporary object have pointers that point to the same memory locations. At the end of BreadthFirstSearch the temporary objects gets destroyed. In the destructor you delete[] vertices and marks.

Now the pointers in the original object point to deallocated memory, which causes undefined behaviour. The easiest solution would be to pass GraphType<string> by reference:

void BreadthFirstSearch(GraphType<string> &graph, string startVertex, string endVertex)

But to be safe it is highly recommended and best practice to use std::vector instead of doing manual memory management.

Answer 2

The problem is that once you have executed your algorithm once the graph ends up with lots of marked vertices. You need to clear the marks for a second execution.