4

Здравствуйте, для представления смежности графа лучше использовать массив сетов или листов? Чем вообще отличается изнутри сет от листа.Спасибо

1

3 ответа 3

9
  1. Как бы смешно это не звучало, но практика показывает, что для представления графа в виде adjacency lists лучше всего подходит std::vector, а не std::list.

  2. В использовании std::set обычно нет необходимости.

  3. Вот выдержка из англоязычного StackOverflow:

    ... в 90% случаев std::vector будет наилучшим выбором. Да, связный список выглядит привлекательнее в подавляющем большинстве случаев, поскольку порядок элементов для него (как правило) несущественен. Иными словами, добавляемые элементы помещаются в конец буфера-контейнера [вне зависимости от места их вставки — прим. пер.], а удаляемый элемент предварительно обменивается местами с конечным, так что вставка и удаление затрагивают только элемент в конце этого буфера.

    Вектор, в свою очередь, копирует свои элементы при каждом расширении своего буфера, однако на практике это несущественно. Экспонециальный рост гарантирует, что среднее количество копирований стремится к некоторой константе, как правило трём или около того.

    Даже если копирование действительно является для вас проблемой (к примеру, элементы имеют большой размер), я всё равно не перешёл бы на связный список. Вместо этого я использовал бы std::deque. Это, по сути, вектор указателей на блоки с элементами. Он редко копирует что-либо при расширении, а если и копирует, то только эти указатели, но не сами элементы. Однако вектор является всё же более предпочтительным выбором, пока вам не требуются возможности, присущие именно деку (вставка в любой из концов и удаление из них); но даже дек предпочтительнее, чем список. Иными словами, сначала std::vector, потом std::deque и только в самом конце std::list.

3
  • 2
    Насчет использования set можно спорить. Зависит от конкретных алгоритмов работы с графом.
    – avp
    15 апр 2012 в 16:48
  • В + set то что он не будет дублировать вершины. 15 апр 2012 в 17:00
  • @avp, плюсую, и от алгоритмов, и даже от особенностей класса графов, рассматриваемых в задаче (если, конечно, это не просто учебное задание).
    – northerner
    15 апр 2012 в 18:34
3

Относительно устройства этих контейнеров. List реализуется как двусвязный список. Set представляет собой автоматически отсортировнный массив элементов. Обычно он реализуется в виде бинарных деревьев, что обеспечивает быстрый поиск нужного элемента. Кроме того, set не допускает дублирования элементов (в отличие от multiset). Более подробно - Джосаттис "С++. Стандартная библиотека."

2

Зависит от желаемого. Обход смежных вершин на списке выполнится не медленнее чем в set или в вектор, зато сэкономит и память, и время в случае разряженного графа.

Опрос "есть ли ребро между вершинами А и Б" на векторе выполнится за постоянное время, на сете за логарифм, на списке линейно.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.