c++ - 第二次在图上运行时，广度/深度优先搜索会导致崩溃

Question

所以我有一个有向图，我在其中添加了顶点和边。该图表示机场及其之间的航类。当我运行广度优先或深度优先搜索来查找两个机场之间的路径时，我第一次得到了正确的答案，但是当我第二次使用完全相同的机场运行它时，它找不到路径并且程序崩溃错误代码-1073741819。我几个小时以来一直试图解决这个问题，但我被难住了。 我运行了调试器，当 BFS 算法进入图形的 IsMarked() 函数时，似乎出现了问题。它无法读取 vertices[] 数组，调试器显示

这是我的图表类

#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;
        }
    }

}

我的广度优先搜索

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;
}

非常感谢任何帮助。非常感谢。

Answer 1

在 void BreadthFirstSearch(GraphType<string> graph, string startVertex, string endVertex)你通过GraphType<string>按值，即创建临时拷贝。那里有指针vertices和marks也会被复制，但不是它们指向的值。

因此原始对象和临时对象具有指向相同内存位置的指针。 月底BreadthFirstSearch临时对象被销毁。在析构函数中你 delete[] vertices和marks 。

现在原始对象中的指针指向已释放的内存，这会导致未定义的行为。 最简单的解决方案是通过 GraphType<string>引用:

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

但为了安全起见，强烈建议最好的做法是使用 std::vector而不是进行手动内存管理。