What is the reason for the std::bad_alloc error when looking in a graph?

Question

C++ / C#

I have a program that performs a breadth-first search and a depth-first search in a graph.

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

The program reads the values ​​of vertices and edges from the in.txt file. The number of vertices and edges is written in the first line, and the paths are written in the rest. The following example is a graph with 4 vertices and 4 edges with paths 0 - 1 - 2 - 3 - 4
4 4
0 1
1 2
2 3
3 4
The program runs properly until the number of edges exceeds 24000, after which error occurs
Unhandled exception at 0x76A7A6E2 in deep.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x008FFA74.
In one of the tests, the program must work with the number of vertices equal to 1000000, which is much more than 24000. Is this error correctable?

Answer 1

Same error as in the previous question. You always put neighboring vertices in the queue in a widthwise bypass, but you should do this only if they are not marked.
You're still waiting in line to pop up ahead of time.