Basic Graph Algorithms

bfs

std::vector<int> BreadthFirstSearch(Graph &graph, int start_vertex) {
  if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
    return {};

  std::vector<int> enter_order;
  std::vector<short> visited(graph.GetVertexesCount());
  std::queue<int> q;

  // Функция принимает вершину, нумерация которой начинается с 1
  // Для удобства уменьшаем ее значение на 1, чтобы нумерация начиналась с 0
  --start_vertex;
  visited[start_vertex] = true;
  q.push(start_vertex);
  enter_order.emplace_back(start_vertex + 1);

  while (!q.empty()) {
    auto from = q.front();
    q.pop();

    for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
      if (!visited[to] and graph(from, to) != 0) {
        visited[to] = true;
        q.push(to);
        enter_order.emplace_back(to + 1);
      }
    }
  }

  return enter_order;
}

DFS

std::vector<int> DepthFirstSearch(Graph &graph, int start_vertex) {
  if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
    return {};

  std::vector<int> enter_order;
  std::vector<short> visited(graph.GetVertexesCount());
  std::stack<int> s;

  --start_vertex;
  visited[start_vertex] = true;
  s.push(start_vertex);
  enter_order.emplace_back(start_vertex + 1);

  while (!s.empty()) {
    auto from = c.top();
    bool is_found = false;

    for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
      if (!visited[to] and graph(from, to) != 0) {
        is_found = true;
        visited[to] = true;
        s.push(to);
        enter_order.emplace_back(to + 1);
        from = to;
      }
    }

    if (!is_found)
      s.pop();
  }

  return enter_order;
}

Note that the code is practically the same, so they can be combined into one function, and just pass the container type there

//
// If Container type = std::stack<int> it will be DepthFirstSearch
// If Container type = std::queue<int> it will be BreadthFirstSearch
//
template <typename Container = std::stack<int>>
std::vector<int> FirstSearch(Graph &graph, int start_vertex)
{
  if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
    return {};

  constexpr bool is_stack = std::is_same_v<Container, std::stack<int>>;

  std::vector<int> enter_order;
  std::vector<short> visited(graph.GetVertexesCount());
  Container c;

  --start_vertex;
  visited[start_vertex] = true;
  c.push(start_vertex);
  enter_order.emplace_back(start_vertex + 1);

  while (!c.empty()) {
    int from = -1;
    if constexpr (is_stack) from = c.top();
    else {
      from = c.front();
      c.pop()
    }

    bool is_found = false;

    for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
      if (!visited[to] and graph(from, to) != 0) {
        is_found = true;
        visited[to] = true;
        c.push(to);
        enter_order.emplace_back(to + 1);
        if (is_stack)
          from = to;
      }
    }

    if (is_stack and !is_found)
      c.pop();
  }

  return enter_order;
}

• Then the BFS & DFS code will look like this:

std::vector<int> BreadthFirstSearch(Graph &graph, int start_vertex) {
  return FirstSearch<std::queue<int>>(graph, start_vertex);
}

std::vector<int> DepthFirstSearch(Graph &graph, int start_vertex) {
  return FirstSearch<std::stack<int>>(graph, start_vertex);
}