Проблема с векторами (std :: out_of_range)

Question

Вот описание моей проблемы:

Описание программы:
Я реализую программу на C ++, которая проверяет алгоритм Prim для поиска минимальных остовных деревьев.Целью программы является вычисление количества секунд, которое требуется, чтобы найти минимальное связующее дерево для выбранного числа случайных графиков.

Что я сделал до сих пор?
Я закончил реализацию функций и файлов заголовков для всей программы.Поскольку исходный код невелик, я решил для ясности вставить его в это письмо, чтобы лучше представить проблему.

Проблема:
По какой-то причине, я столкнулся с какой-то векторной проблемой «вне диапазона» во время выполнения приложения.Проблема отмечена в файле ("Prim_and_Kruskal_Algorithms.cpp").

Запрос справки:
Я был бы очень признателен, если кто-нибудь может помочь мне определить проблему.Я добавил исходный код с этим вопросом.

Исходный код:

Файл (Undirected_Graph.h):

#ifndef UNDIRECTED_GRAPH_H
#define UNDIRECTED_GRAPH_H

#include <vector>
using std::vector;

#include <climits>

class Edge;

class Node
{
    public:

        Node(int);                 //The constructor.

        int id;                    //For the id of the node.
        bool visited;              //For checking visited nodes.
        int distance;

        vector <Edge*> adj;       //The adjacent nodes.
};

class Edge
{
    public:

        Edge(Node*, Node*, int);   //The constructor.

        Node* start_Node;          //The start_Node start of the edge.
        Node* end_Node;            //The end of the edge.
        int w;                     //The weight of the edge.

        bool isConnected(Node* node1, Node* node2)  //Checks if the nodes are connected.
        {
            return((node1 == this->start_Node && node2 == this->end_Node) ||
                   (node1 == this->end_Node   && node2 == this->start_Node));
        }
};

class Graph
{
    public:

        Graph(int);                    //The Constructor.

        int max_Nodes;                 //Maximum Number of allowed Nodes.

        vector <Edge*> edges_List;     //For storing the edges of the graph.
        vector <Node*> nodes_List;     //For storing the nodes of the graph.

        void insertEdge(int, int, int);

        int getNumNodes();
        int getNumEdges();
};

#endif

(Файл Undirected_Graph.cpp):

#include "Undirected_Graph.h"

Node::Node(int id_Num)
{
    id = id_Num;
    visited = 0;
    distance = INT_MAX;
}

Edge::Edge(Node* a, Node* b, int weight)
{
    start_Node = a;
    end_Node = b;
    w = weight;
}

Graph::Graph(int size)
{
    max_Nodes = size;

    for (int i = 1; i <= max_Nodes; ++i)
    {
        Node* temp = new Node(i);

        nodes_List.push_back(temp);
    }
}

void Graph::insertEdge(int x, int y, int w)
{
    Node* a = nodes_List[x-1];
    Node* b = nodes_List[y-1];

    Edge* edge1 = new Edge(a, b, w);
    Edge* edge2 = new Edge(b, a, w);

    edges_List.push_back(edge1);

    a->adj.push_back(edge1);
    b->adj.push_back(edge2);
}

int Graph::getNumNodes()
{
    return max_Nodes;
}

int Graph::getNumEdges()
{
    return edges_List.size();
}

Файл (Prim_and_Kruskal_Algorithms.h):

#ifndef PRIM_AND_KRUSKAL_ALGORITHMS_H
#define PRIM_AND_KRUSKAL_ALGORITHMS_H

class PKA
{
    private:
    //inline void generateRandomGraph();

    protected:
    //-No Protected Data Members in this Class.

    public:
        void runAlgorithms();
        void prim();
};

#endif

(Prim_and_Kruskal_Algorithms.cpp)файл * (проблема в этом файле и помечена ниже): *

#include "Prim_and_Kruskal_Algorithms.h"
#include "Undirected_Graph.h"

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#include <cstdlib>
using std::rand;
using std::srand;

#include <ctime>
using std::time;

//=============================================================================
//============Global Variables and Settings for the program====================
//=============================================================================

const int numIterations = 1; //How many times the Prim function will run.
const int numNodes = 10;     //The number of nodes in each graph.
const int numEdges = 9;      //The number of edges for each graph.
const int sRandWeight = 1;   //The "start" range of the weight of each edge in the graph.
const int eRandWeight = 100; //The "end" range of the weight of each edge in the graph.

//=============================================================================
//=============================================================================
//=============================================================================

void PKA::runAlgorithms()   //Runs the Algorithms
{
        srand( time(0) );

    cout << "------------------------------" << endl;

        //Calling the Functions:
        cout << "\nRunning the Prim's Algorithms:\nPlease wait till the completion of the execution time" << endl;

        //===============================================

        //Start the clock for Prim's Algorithm:
        clock_t start, finish;
        start = clock();

        for(int iter1 = 1; iter1 <= numIterations; ++iter1)
        {
            prim();
        }

        //Stop the clock for Prim and print the results:
    finish = clock();
        cout << "\n\tThe execution time of Prim's Algorithm:\t" << ((double)(finish - start) / CLOCKS_PER_SEC) << " s";

    return;
}

void PKA::prim()
{
    //=============================================================================
    //=============================Generating A Random Graph=======================
    //=============================================================================

    //Randomizing Values:
    //===============================================

    int randStartNode = rand() % numNodes;     //Generation a random start node.
    int randEndNode = rand() % numNodes;       //Generating a random end node.
    int randWeight;               //Random weight for the edge.

    while(randEndNode == randStartNode)   //Checking if both randomized nodes are equal.
    {
        randEndNode = (rand() % numNodes);
    }

    //===============================================

    Graph myGraph(numNodes);

    for(int i = 0; i < numEdges; ++i)
    {
        //Generating a random weight:
        randWeight =  sRandWeight + rand() % eRandWeight;

        //Inserting a new Edge:
        myGraph.insertEdge(randStartNode, randEndNode, randWeight);
    }


    //=============================================================================
    //=============================================================================
    //=============================================================================

    int currentNode = 0;           //The current Node being under investigation.
    int adjCounter = NULL;         //How many adjacent nodes do we have for the current node.
    int minDistance = NULL;        
    int minIndex = 0;

    myGraph.nodes_List[0]->distance = 0;   //Indicate the start node.
    myGraph.nodes_List[0]->visited = 1;    //The starting node is already considered as a visited node.

    for(int i = 0; i < numNodes - 1; i++)
    {
        //Determine how many adjacent nodes there are for the current node:
        adjCounter = myGraph.nodes_List[currentNode]->adj.size();

        if(adjCounter == 0) //If there are no adjacent nodes to the current node:
        {
            myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;
                    cout << "\n*******Not all nodes are connected!*******" << endl;
            continue;
        }

        minDistance = myGraph.nodes_List[currentNode]->adj.at(0)->w;
        minIndex = 0;

        for(int counter = 0; adjCounter > 0; adjCounter--, counter++)
        {
            if(myGraph.nodes_List[currentNode]->adj[counter]->end_Node->visited == false)
            {
                if(myGraph.nodes_List[currentNode]->distance > myGraph.nodes_List[currentNode]->adj[counter]->w)
                {
                    myGraph.nodes_List[currentNode]->distance = myGraph.nodes_List[currentNode]->adj[counter]->w;
                }

                if(minDistance > myGraph.nodes_List[currentNode]->adj[counter]->w)
                {
                    minDistance = myGraph.nodes_List[currentNode]->adj[counter]->w;
                    minIndex = counter;
                }
            }
        }

                //======================================================================================
                //=========================The Problem is in the following two lines====================
        //======================================================================================

        //Mark the current node as visited:
        myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;

        //Switching to the next node that we have just visited:
        currentNode = myGraph.nodes_List[currentNode]->adj.at(minIndex)->start_Node->id;

        //======================================================================================
        //======================================================================================
        //======================================================================================
    }
}

Файл (Client_Code.cpp): для тестирования программы.

#include "Prim_and_Kruskal_Algorithms.h"
#include <iostream>

using std::cout;
using std::endl;

int main()
{
    cout << "\nWelcome to the Prim and Kruskal Algorithms Comparison!" << endl;
    cout << "\nPlease wait until the completion of the algorithms." << endl;

    PKA myPKA;                //Creating an object of the class.
    myPKA.runAlgorithms();    //Running the Algorithm.

    cout << "\n\nThe program terminated successfully!" << endl;

    return 0;
}

Answer 1

Посмотрите на эту строку:

myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;

Как опытный программист на C ++, я нахожу эту строку ужасающей.

Непосредственной причиной проблемы является то, что adj не имеет столько членов, сколько вы думаете; вы запрашиваете (в моем тестовом прогоне) 5-й элемент списка нулевого размера. Это отправляет вас с карты, где вы начинаете манипулировать памятью.

В целом, вы не проверяете границы.

В целом, вы должны разрешить этим классам управлять своими собственными членами. Используйте аксессоры и мутаторы (getX() и setX(...)), чтобы доступ к элементам происходил в одном месте, и вы можете поставить проверку границ там. Дотянуться до горла myGraph очень небезопасно.

Вы заметите, что я не сказал где / когда / как программа отклоняется от намерения, поэтому в списке не так много элементов, как должно. Это потому, что мне слишком сложно отследить это. Если вы организуете классы, как я предлагаю, код станет намного чище, вы сможете проверить свои предположения в разных местах, и ошибка должна стать очевидной.

EDIT:
Чтобы создать случайный связный граф, попробуйте это:

  Graph myGraph(numNodes);              //Create a new Graph.

  // This ensures that the kth node is connected to the [1...(k-1)] subgraph.
  for(int k=2 ; k<=numNodes ; ++k)
    {
      randWeight =  rand() % eRandWeight;
      myGraph.insertEdge(k, rand()%(k-1)+1, randWeight);
    }

  // This adds as many extra links as you want.
  for(int i = 0; i < numExtraEdges; ++i)
    {
      randWeight =  rand() % eRandWeight;
      randStartNode = rand()%(numNodes-1)+1;
      randEndNode = rand()%(numNodes-1)+1;
      myGraph.insertEdge(randStartNode, randEndNode, randWeight);
    }

Answer 2

У вас слишком много кода для случайного обследования, чтобы быть уверенным в чем-либо. Но метод .at() сгенерирует исключение за пределами допустимого диапазона, о котором вы упомянули, и эта строка сбоя произойдет сразу после того, как вы обновите minIndex, поэтому я бы предложил пересмотреть код, который определяет это значение. Вы используете отладчик? Каково значение minIndex в точке исключения и каков допустимый диапазон?

Кроме того, если у вас есть огромная строка составных операторов, это может помочь в отладке подобных проблем и дать вам более понятный и простой код, если вы разберетесь с ним. Вместо того, чтобы повторять большие куски кода снова и снова, вы можете получить что-то вроде этого:

Node * node = myGraph.nodes_List[currentNode];
assert(node);
Edge * minAdjEdge = node->adj.at(minIndex);
assert(minAdjEdge);

Затем используйте minAdjEdge для ссылки на это ребро вместо этого повторного составного оператора.

Мне также кажется странным, что ваше первое использование minIndex в большом цикле все еще использует значение, определенное для узла в предыдущей итерации, но применяет его к новому текущему узлу. Затем вы сбрасываете его в ноль после возможного использования устаревшего значения. Но это не близко к линии, которая, как вы говорите, вызывает сбой, так что это может не быть вашей проблемой. Как я уже сказал, у вас есть много кода, вставленного сюда, поэтому трудно следить за всем этим.

Answer 3

Это слишком много кода, но на первый взгляд я вижу, что по какой-то причине вы смешиваете итерацию на основе 0 и 1.

Это намеренно?Разве это не может быть причиной вашей проблемы?