В чем проблема обхода в ширину и глубину?

Question

[NoName]

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

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

using namespace std;

UINT BFS(UINT begin, UINT vertex, UINT n,  const vector<vector<int>> &graph)
{
   queue<int> q;
   q.push(begin);


   set<int> gray;

   while (!q.empty())
   {
      UINT v = q.front();
      q.pop();
      gray.insert(v);

      if (v == vertex)
         return 1;

      for (UINT i = 0; i < n; i++)
         if (graph[v][i])
            q.push(i);
      
      if (q.empty())
         return 0;
   }
   for (UINT j : gray);
}



UINT DFS(UINT u, UINT vertex, UINT n,  const vector<vector<int>> &graph, set<int> &gray, set<int> &black)
{
   gray.insert(u);

   for (UINT i = 0; i < n; i++)
      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)
            is_white = 1;


         if (is_white)
            if (DFS(i, vertex, n, graph, gray, black))
               return 1;
      }
   
   gray.erase(u);
   black.insert(u);

   return 0;
}



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

   ifstream get_content("in.txt");

   if (get_content)
   {
      UINT vertex, edge;
      get_content >> vertex >> edge;
      vector<vector<int>> graph;
      graph.assign(vertex, vector<int>(vertex));;

      UINT one, two;

      for (UINT i = 0; i < edge; i++)
      {
         UINT one, two;
         get_content >> one >> two;
         graph[one][two] = 1;
      }
      


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

      cin >> one;
      cin >> two;

      set<int> gray, black;


      UINT b = DFS(one, two, vertex, graph, gray, black);
      
      b ? printf_s("Путь есть\n") : printf_s("Пути нет\n");


      b = BFS(one, two, vertex, graph);


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

   }
   else
      printf_s("Не удалось открыть файл");

   return;
}

В файл in.txt в первую строку записывается число вершин и ребер, далее записываются пути из одних вершин в другие
В ходе тестирования обнаружилось, что при вводе в in.txt:
4 4 //4 вершины и 4 ребра
0 1
1 2
2 0
2 3
Программа при поиске пути из вершины 0 в вершину 3(Путь есть) выдает ошибку. В чем может быть проблема? Буду благодарен за предоставление исправленного участка кода

Comments

[Wataru]

Какую ошибку выдает?

Answer 1

[Wataru]

В BFS вы не проверяете, что вершина помечена, и всегда кладете вершину в очередь. А еще там в конце какой-то левый цикл ненужный. Поиск бесконечно циклится и съедает всю память. DFS, похоже, правильный (есть много претензий к стилю, правда).

Comments

[NoName]

Я закомментировал строку:

//UINT b = DFS(one, two, vertex, graph, gray, black);
      
      //b ? printf_s("Путь есть\n") : printf_s("Пути нет\n");


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


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

Поиск в ширину выдал верный результат, значит проблема именно в DFS

[Wataru]

NaName444, (!is_black || !is_gray) всегда true в вашем случае. Там должно быть &&