В чем причина возникновения ошибки std::bad_alloc при поиске в графе?

Question

[NoName]

Имеется программа, осуществляющая поиск в ширину и в глубину в графе

#pragma once

#include <vector>
#include <locale.h>
#include <queue>
#include <Windows.h>
#include <set>
#include <iostream>
#include <fstream>
#include <ctime>


using namespace std;

UINT breadthFirstSearch(vector<vector<UINT>> &graph, UINT begin, UINT vertex, UINT n)
{
   queue<UINT> q;
   q.push(begin);// Поместить узел, с которого начинается поиск, в изначально пустую очередь.

   set<int> gray;

   while (!q.empty())
   {
      UINT i = 0;

      q.pop();
      gray.insert(q.front());

      if (q.front() == vertex)
         return 1;

      while (i < n)
      {
         if (graph[q.front()][i])
            q.push(i);

         i++;
      }

      if (q.empty()) return 0;
   }
}


UINT depthFirstSearch(vector<vector<UINT>> &graph, set<UINT> &gray, set<UINT> &black, UINT u, UINT vertex, UINT n)
{
   gray.insert(u); // перекрашиваем вершину в серый цвет

   UINT i = 0;

   while (i < n)
   {
      if (graph[u][i])
      {
         if (i == vertex)
            return 1;

         int is_black = black.count(i), is_gray = gray.count(i), is_white = 0;


         if (!is_black && !is_gray)// Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру
            is_white = 1;

         if (is_white)
            if (depthFirstSearch(graph, gray, black, i, vertex, n))
               return 1;
      }

      i++;

   }
   gray.erase(u); //удаление вершины из множества gray

   black.insert(u);//добавление вернишы в множество black Перекрашиваем вершину u в чёрный цвет

   return 0;
}







void main()
{
   UINT one = 0, two = 0;
   setlocale(LC_ALL, "");

   ifstream get_content("in.txt");

   UINT vertex, edge;

   get_content >> edge;
   get_content >> vertex;

   vector<vector<UINT>> graph;

   graph.assign(vertex, vector<UINT>(vertex));;// замена всех элементов вектора набором из вершин

   UINT i = 0;


   while(i < edge)
   {
      UINT one, two;
      get_content >> one;
      get_content >> two;
      graph[one][two] = 1;

      i++;
   }

   printf_s("Введите две вершины: ");

   cin >> one;
   cin >> two;

   set<UINT> gray;//множество отсортированных значений
   set <UINT>black;

   unsigned int start_time = clock(); // начальное время

   UINT b = depthFirstSearch(graph, gray, black, one, two, vertex);

   unsigned int end_time = clock(); // конечное время
   unsigned int search_time = end_time - start_time;

   printf_s("%d ", search_time);

   b ? printf_s("Путь есть\n") : printf_s("Пути нет\n");

   UINT b = breadthFirstSearch(graph, one, two, vertex);

   b ? printf_s("Путь есть\n") : printf_s("Пути нет\n");


  
   return;
}

Значения вершин и ребер программа читает из файла in.txt.В него в первую строку записывается число вершин и ребер, в остальные - пути. Далее представленный пример - это граф с 4 вершинами и 4 ребрами с путями 0 - 1 - 2 - 3 - 4
4 4
0 1
1 2
2 3
3 4
Программа работает исправно до того момента, пока число ребер не превышает значение 24000, после чего возникает ошибка
Unhandled exception at 0x76A7A6E2 in deep.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x008FFA74.
В одном из тестов программа должна работать с количеством вершин, равным 1000000, что значительно больше, чем 24000. Исправима ли данная ошибка?

Answer 1

[Wataru]

Та же ошибка, что и в прошлом вопросе. Вы в очередь в обходе вширину всегда кладете соседние вершины, а надо это делать, только если они не помечены.

Вы там еще очередь pop-аете раньше времени.

Comments

[NoName]

Простите, данная ошибка возникает даже в случае запуска только обхода в глубину

[NoName]

Данная ошибка возникает даже при отсутствии запуска обоих функций

[NoName]

Она возникает на этапе инициализации графа и добавлении в него вершин

vector<vector<ULONGLONG>> graph;

graph.assign(vertex, vector<ULONGLONG>(vertex));;

[Wataru]

NaName444, Ах, вы тут заводите матрицу смежности. Сколько вершин-то у вас? Памяти может не хватить. Храните вместо матрицы - списки смежности. Для каждой вершины храните номера связанных с ней, а не 0/1 по всем возможным индексам.