Вопрос: Как преподаются графики?

Question

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

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

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

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

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

Спасибо !!

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

calloc(number_of_nodes, sizeof(struct vertex));

Я не уверен (на относительно более низком уровне) внутри компилятора, что / как реализовано это распределение памяти - будь то список / набор / карта.

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

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

Answer 3

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

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

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

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

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