С#. Алгоритм Прима (lazy вариант)

Git

Своими словами.

Обходятся все вершины. Для каждой вершины выбираются инцидентные ребра.

Просматриваются противоположные вершины инцидентных ребер и добавляются в очередь.

Просматривается очередь и выбирается ребро с наименьшим весом.  Оно добавляется в финальную очередь.

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

Но есть 2 реализации алгоритма Прима – ленивая (ребра, образующие циклы не исключаются сразу) и энергичная (ребра, образующие циклы, исключаются сразу)

Теперь немного теории из Сэйджвика

Continue reading

Posted in C# | Leave a comment

C#. IEnumerable. Пример реализации

Делал индексную очередь с приоритетами, понадобилось реализовывать интерфейс IEnumerable. Получилось так

Понадобилось реализовать 2 следующих метода

В контексте логики класса был написан другой класс HeapIterator Continue reading

Posted in C# | Leave a comment

C#. Индексная очередь с приоритетами

Git
Continue reading

Posted in C# | Leave a comment

C#. Очередь с приоритетами на бинарной пирамиде

Git

В данном разделе рассмотрим теорию из Сейджвика про очередь с приоритетами и бинарную пирамиду. Последнюю используем в качестве структуры данных для реализации очереди с приоритетами.

В данном случае напишем очередь, которая поддерживает

  • вставку элемента
  • получение элемента с максимальным ключом

Идея алгоритма в том, что в качестве бинарной пирамиды мы будем использовать массив. В этот массив мы будем вставлять данные и получать их из него. При каждой вставке, получении, целостность пирамиды у нас будет возможно нарушаться, поэтому мы будем частично обходить пирамиду для восстановления целостности. Такой обход будет стоить логарифмического времени.  Что позволит работать с огромными данными.

По сути, если пройтись циклом, доставая из контейнера все данные, мы получим отсортированные данные. В данном примере по убыванию. Но, нетрудно переписать алгоритм и для возрастающего случая, для этого надо доставать каждый раз из хранилища данные с минимальным ключом.
Continue reading

Posted in C# | Leave a comment

C#. EdgeWeightedGraph. Граф со взвешенными ребрами

Git

Рассмотрим такой граф

Представление в текстовом файле будет таким

 

Напишем вспомогательный класс Edge Continue reading

Posted in C# | Leave a comment

C#. IEnumerable. Пример использования

На примере поиска цикла в графе

В другом классе используем так…

 

Posted in C# | Leave a comment

С#. Минимальные остовные деревья. Теория

Из Сейджвика, раздел 4.3 Минимальные остовные деревья



Continue reading

Posted in C# | Leave a comment

C#. Сейджвик, орграфы, некоторые упражнения

Каково максимальное количество ребер E в орграфе с V вершинами и без параллельных ребер?

Вероятно, E=V; Но возможны петли.


Нарисовать по аналогии для входного потока  Continue reading

Posted in C# | Leave a comment

C#. Сильно связные компоненты в орграфе, алгоритм Косараю

Git

Сложность алгоритма Косараю V+E

Рассмотрим граф

Серым цветом отмечены области сильно связных компонентов. Continue reading

Posted in C# | Leave a comment

C#. Топологическая сортировка

Git

Сейджвик, стр. 522

Continue reading

Posted in C# | Leave a comment