Основные алгоритмы на графах03.08.2023 17:31

BFS

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

  std::vector enter_order;
  std::vector visited(graph.GetVertexesCount());
  std::queue 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 DepthFirstSearch(Graph &graph, int start_vertex) {
  if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
    return {};

  std::vector enter_order;
  std::vector visited(graph.GetVertexesCount());
  std::stack 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;
}

Заметим, что код практически ничем не отличается, поэтому их можно объединить в одну функцию, и передавать туда просто тип контейнера

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

  constexpr bool is_stack = std::is_same_v>;

  std::vector enter_order;
  std::vector 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;
}

Тогда код BFS & DFS будет выглядеть так:

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

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