<reponame>siarheidubouski/QtMazeGenerator<filename>src/generation_algorithms/bfs.cc
#include <iostream>
#include <algorithm>
#include "BFS.h"

std::vector<std::pair<int, int>> BFS::createSpanningTree(
    int vertices, const Graph& adjList) {

  visited_ = std::vector<bool>(vertices, false);

  int startVertex = std::uniform_int_distribution<int>(0, vertices - 1)(generator);

  currentLevel_.push_back(startVertex);
  visited_[startVertex] = true;

  spanningTree_.clear();

  while (!currentLevel_.empty()) {
    for (auto vertex: currentLevel_) {
      for (const auto& edge: adjList[vertex]) {
        int nextVertex = edge.first;

        if (nextVertex < 0 || visited_[nextVertex]) {
          continue;
        }

        visited_[nextVertex] = true;
        spanningTree_.push_back({vertex, nextVertex});
        nextLevel_.push_back(nextVertex);
      }
    }

    currentLevel_.clear();
    std::swap(currentLevel_, nextLevel_);
    std::shuffle(currentLevel_.begin(), currentLevel_.end(), generator);
  }

  return spanningTree_;
}
