@NaName444

Как оптимизировать поиск в ширину?

Имеется программа, осуществляющая поиск в ширину и в глубину в ориентированном графе. Граф в файл записывается так:
4 4 : число вершин и ребер
0 1
1 2
3 4: Существующие пути между вершинами
#pragma once

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


using namespace std;

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

   set<bool> gray;

   while (!q.empty())
   {
      q.pop();
      UINT c = q.front();

      gray.insert(c);

      if (c == vertex)
         return 1;

      for(UINT i = 0;i < n;i++)
         if (graph[c][i])
            q.push(i);

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


bool depthFirstSearch(const vector<vector<UINT>> &graph, set<bool> &gray, set<bool> &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)
            is_white = 1;

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

      i++;

   }
   gray.erase(u); 

   black.insert(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<bool> gray;
   set <bool>black;

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

    b = breadthFirstSearch(graph, 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");

    start_time = clock();


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

   unsigned int end_time = clock();
   unsigned int search_time = end_time - start_time;


Проблема в том, что поиск в ширину работает почти в 3 раза медленнее, хотя в теории должен работать с такой же скоростью, что и поиск в глубину. Как оптимизировать данный алгоритм? Желательно привести исправление в коде
  • Вопрос задан
  • 47 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Мне в третий раз повторить?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы