Вопрос о том, как преподаются графики

Question

Я из Аргентины, но я думаю, что каждый, кто когда -либо принимал класс структур данных, знают, что такое график. Если вы это сделаете, вы можете знать, какие реализации являются «общими» или «стандартными». Это может быть реализовано через список или массив. Даже Википедия говорит это. А также Марк Аллен Вайс, Бруно Прейсс и Луис Джойанс Агилар.

Дело в том. Никто никогда не думал, что это не хороший способ сделать это? Наиболее рекомендуемый способ - через список. Но считая, что вершины могут иметь только один край между ними, я не думаю, что список - это хороший интерфейс для этого. Я имею в виду, если Vertex V1 связан с Vertex V2, то есть только один и только один край.

Разве вы не думаете, что это будет набор вместо списка?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

Просто хотите узнать некоторые мнения, как вы думаете?

Спасибо!!

Редактировать: Кроме того, если мы думаем, что график не может иметь повторяющиеся элементы, хэшсет был бы хорошим выбором, чтобы минимизировать поиск вершины в вставке.

Answer 1

Вы правы, указав, что прилегающие стороны для вершины наиболее точно смоделированы с помощью набора (или в случае мультиграфа, мультисет). Так почему же книги «Структуры данных» пишут о массивах и связанных списках вместо этого? Я могу вспомнить три причины:

1. Идея о том, что языки программирования должны включать наборы в качестве примитивного типа данных, довольно недавно. Пожилые писатели не рассматривали бы его использование, и современные писатели склонны следовать традициям поля.

2. Одной из целей курса структур данных является возможность подумать о представлении данных на низком (конкретном) уровне, а также на высоком (абстрактном) уровне. Набор-это абстрактный данных, который (в отличие от связанных списков и массивов) не имеет очевидной реализации низкого уровня: некоторые наборы лучше всего представлены в виде связанных списков, некоторые как хэш-таблицы, некоторые как массивы и т. Д. Таким образом, для курса структур данных естественно пропустить высокоуровневое представление наборов в их реализации низкого уровня, о которой вы должны знать в любом случае, чтобы проанализировать поведение алгоритмов, которые их используют.

3. Важно не быть догматичным в отношении того, как представлять данные дата, потому что алгоритмы могут быть наиболее эффективно выражены с использованием конкретных представлений. Пример 1. Подсчитать пути длины не Между каждой парой вершин на графике представьте график по его смежному матрицу и поднимайте матрицу к власти не. Анкет Если вы настаиваете на том, чтобы представлять смежность вершины в виде набора краев, то вы пропустите этот алгоритм (который может быть параллельно с использованием стандартных методов). Пример 2. Кнут "Танцующие ссылки«Алгоритм для точной задачи обложки представляет наборы столбцов с использованием дважды связанных списков, так что ссылки из удаленных элементов могут быть использованы повторно для эффективного возврата.

Answer 2

В относительно выше C/C ++ Уровень программиста, как реализован график/сеть, в значительной степени зависит от того, какие операции выполняются на нем. Будучи самому человеку, я, вероятно, предвзято в своем ответе/примере здесь. Некоторые из наиболее эффективных алгоритмов, которые могут быть реализованы на графиках/сетях, являются алгоритмами полиномиального времени. Большинство, если не все, алгоритмы полиномиального времени, о которых я могу подумать (проблема с кратчайшим пути Dijkstra, проблема транспорта, проблема с максимальным потоком и т. Д.), являются особыми случаями проблемы с минимальной стоимостью (MCF). Вычислительно, одним из наиболее эффективных способов решения проблемы MCF является алгоритм сети-симплекса (который сам по себе является специализацией алгоритма Simplex по решению общей линейной программы).

В сети-симе-алгоритме необходимо эффективно представлено охраняющее дерево (над набором узлов). Чтобы представить охватывающее дерево в графике, можно использовать различные структуры данных. Они включают в себя следующую длину узла

predecessor[], thread[] and depth[] arrays.

В наиболее эффективных реализациях сетевых-симплекс-алгоритмов, с которыми я столкнулся, они не представлены как массивы, а какой-то динамически созданный блок памяти через

calloc(number_of_nodes, sizeof(struct vertex));

Я не уверен (на относительно ниже Уровень) Внутренний для компилятора Что/как реализовано это распределение памяти - будь то список/Set/Map.

Итак, в итоге, Лучший Способ реализации графика сильно зависит от операций, которые будут выполнены на нем.

Алгоритм простого простого сети и структуры данных, необходимые для эффективного реализации, могут быть найдены в эта книга.

Answer 3

В наиболее абстрактном, набор имеет предикат, чтобы проверить, находится ли элемент внутри набора. Это также может поддержать операторов, которые обеспечивают союз и перекресток. Разница не требуется вычисляемо.

В своем наиболее абстрактном списке поддерживает итерацию, суб-списки и добавление.

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

Конечно, большинство наборов в библиотеках являются конечными, удлинительными наборами, которые также поддерживают итерацию, поэтому вы можете использовать их, хотя у вас все еще будет стоимость проверки дубликатов.

Некоторые системы на графиках используют наборы в качестве базового механизма, но они занимаются бесконечными графами, а не конечными, где интенсивные наборы становятся полезными.