Графы-1: списки смежности, поиск в ширину

Цель

Понять, что такое представление графа, называемое «списки смежности». Научиться его реализовывать на C++, использовать его для организации поиска.

Код

Итак, определим класс, реализующий представление ориентированного графа в виде списков смежности. Он будет содержать некоторую базовую функциональность, позволяющую управлять содержимым представления, и функцию bfs, выполняющую поиск в ширину.

Пока будем считать, что вершина – это просто номер. Список смежности вершины находится в массиве по соответствующему индексу.

/// naive Adjacency Lists implementation
class AdjacencyLists
{
public:
  /// vertex representation, just its index for now
  typedef std::size_t Vertex;

Принято называть набор соседей «списком смежности», однако нетрудно видеть, что в нашем случае удобнее использовать библиотечный класс set, чем list. Собственно «представление» есть массив (vector) «списков смежности».

private:
  typedef std::set<Vertex> Adjacency;
  typedef std::vector<Adjacency> Repr;
  Repr repr; // the representation itself

Элементарный конструктор, позволяющий сразу задать количество вершин в графе (по умолчанию –  ноль).

public:
  /// acquire space for the given amount of vertices
  explicit AdjacencyLists(std::size_t vertices_ = 0u)
    : repr(vertices_) {}

Далее идут простейшие функции, позволяющие управлять представлением. Например, проверка графа на пустоту и запрос количества вершин в графе:

  /// tests if there are any vertices
  bool empty() const
  {
    return repr.empty();
  }

  /// tell us, how many vertices are there
  std::size_t vertices() const
  {
    return repr.size();
  }

Нерекурсивный (использует стандартный класс queue) поиск в ширину. Начинает с вершины start. Для каждой найденной вершины вызывает функтор visit.

  /// breadth-first search
  /**
   * @param visit the functor to be called for each vertex
   * @param start the vertex to start search from
   * @return how many vertices have been visited 
   */
  template<class Visitor>
  std::size_t bfs(Visitor visit, Vertex start) const
  {
    if (vertices() <= start)
      return 0u;

    std::vector<bool> visited(vertices(), false);
    std::queue<Vertex> Q;
    Q.push(start);

    std::size_t res = 1u;
    visit(start);
    visited[start] = true;

    while (!Q.empty())
    {
      const Vertex v = Q.front();
      Q.pop();
      for (const Vertex w : repr[v]) // C++11
      {
        if (!visited[w])
        {
          Q.push(w);
          visit(w);
          visited[w] = true;
          ++res;
        }
      }
    }

    return res;
  }
};

Возможный код небольшого теста поиска в ширину. Должны быть
последовательно выведены числа от 0 до 12.

template <class T>
void println(const T &what)
{
  std::cout << what << "\n";
}

void test1()
{
  // 12 vertices
  Graphs::AdjacencyLists G(12);

  // add edges
  G.biconnect(0, 1);
  G.biconnect(0, 2);
  G.biconnect(0, 3);
  G.biconnect(1, 4);
  G.biconnect(1, 5);
  G.biconnect(3, 6);
  G.biconnect(3, 7);
  G.biconnect(4, 8);
  G.biconnect(4, 9);
  G.biconnect(6, 10);
  G.biconnect(6, 11);

  // should result into numbers 0 … 12
  std::cout << G.bfs(println<unsigned>, 0);
}

Этот же код целиком: codepad.

 

Задания

  1. Прочитать и понять приведённый код. Почему в конце выводится число 12?
  2. Реализовать поиск в глубину аналогично реализованному поиску в ширину bfs.
  3. Как использовать bfs, чтобы определить связность графа?
  4. Написать код, использующий bfs для выделения компонент связности.
  5. Найти недостатки приведённой выше реализации.
  6. Написать тест на скорость работы, позволяющий сравнить std::set и std::unordered_set (C++0x) или boost::unordered_set в качестве реализации «списка смежности».
Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: