Delphi. Алгоритмы. DFS. Поиск в глубину рекурсивно

Своими словами. Берем первую вершину, смотрим, нет ли у нее инцидентных ребер (прямых потомков), если есть помечаем, повторяем процедуру для найденной вершины, и так до конца глубины. Возвращаемся, идем к соседней вершине, и так далее.

interface

init visited array

dfs

Теперь, если наш граф не дерево с единственным корнем, обходим по всем узлам

 

Delphi. Алгоритмы. BFS — обход графа в ширину

Теория хорошо описана на Вики.  Суть в этой гифке ниже.

 

Моя скромная реализация для представления графа в виде матрицы смежности. Ноль в матрице смежности означает отсутствие ребра между вершинами. Единица — наличие.  В основе обхода в ширину — такая структура как очередь. Первым вошел, первым вышел.

Своими словами (самое ценное, когда своими словами).

1 Берем стартовую вершину. Добавляем ее в очередь.

2 Ищем у этой вершины все инцидентные ребра.  Добавляем их в очередь.

3 При добавлении каждой вершины что-то делаем.

4 Первая вершина отработала, удаляем ее из очереди.

5 Берем следующую по очереди вершину (в моей реализации left+1) и повторяем с п. 2

 

Также рандомная инициализация BFS

Список источников, которые мне помогли)

Отличная тема на форуме

 

Delphi.DBTreeView. Алгоритм динамического обновления узлов

Пусть есть TreeView, связанное с базой данных, например MySQL. Необходимо сделать так, чтобы данные загружались только при первоначальном заполнении (idParent=-1) либо при раскрытии узла (OnExpanding).

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

Итак, человеческими словами

Алгоритм

-собрать ID и имена всех детей для определенного родителя

-очистить узел от указателей и детей

-загрузить данные в узел, добавляя в свойство Node.Data ссылку на ID узла в базе. Для большинства задач этого достаточно, если нужно больше данных, можно использовать ссылку на запись или экземпляр класса, если уж все будет совсем масштабно.

-при загрузке проверять, если у какого-то ребенка есть еще дети, добавлять «призрачный» узел, чтобы у TreeView появлялся «плюсик», при нажатии на который можно производить очередной Expanding Читать далее «Delphi.DBTreeView. Алгоритм динамического обновления узлов»

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

-пусть есть TreeView, соединенный с базой, скажем MySQL

-пусть мы хотим удалить выделенный узел TreeView из базы данных и из дерева

Алгоритм (пока что №1 в моем рейтинге)

-собрать ID всех детей (рекурсивно), хранящиеся по указателю каждого узла дерева SomeNode.Data

-удалить все записи с этими ID из БД

-удалить указатели всех детей в TreeView обычным обходом всех детей через repeat until

-удалить всех детей из дерева

-удалить указатель удаляемого узла

-удалить сам узел

Вот пример из одной из программ Читать далее «Delphi. DBTreeView. Самый эффективный алгоритм удаления узлов из дерева, связанного с базой данных»

Delphi. Алгоритмы. Галерея своими руками или как выложить плитками фрэйм

Давно хотел записать это, так как часто пригождается, думаю транслировать на другие языки не составит труда. Итак, вот что у нас получится…

61

Я пока не стал выкладывать никакие картинки, просто хочу здесь описать саму логику алгоритма. Сам алгоритм я взял в книге Дмитрия Осипова по FireMonkey и немного адаптировал под свою задачу.

Итак, пусть есть N картинок заданного размера. Я создал отдельный объект фиксированного размера TPictureFrame и им выложил галерею так, чтобы если плитка не входит — она перемещалась бы на следующий ряд. Саму плитку раскрасил белым и окантовал серым.

Алгоритм выкладывания плиток

Читать далее «Delphi. Алгоритмы. Галерея своими руками или как выложить плитками фрэйм»

Delphi. Алгоритмы. Создание уникального имени через добавление номера в конце в скобках. Например SomeFile(1), SomeFile(2) и др.

Итак, пусть у нас в некоторой директории находится файл SomeFile, сделаем так, чтобы при добавлении следующего файла с именем SomeFile, в директории оказался файл SomeFile(1), SomeFile(2), SomeFile(3). При отсутствии этого файла в директорию копируется просто файл. Данная задача возникла в результате разработки решения для передачи файлов по HTTP протоколу. Нужно было сделать так, чтобы при каждой передаче файл в обязательном порядке копировался и сохранялся под новым именем в любом случае, даже если он там уже есть. Не перезаписывал существующий, а создавал новый, с каким-то другим именем.

Первоначально задача показалась мне тривиальной, пока я не начал ее решать. Впоследствии я понял, что там множество других маленьких задач. Вот что у меня получилось.

Основная функция

Здесь у нас список имен, с которыми нужно сравнивать, это имена из директории. А также само имя, которое должно быть уникальным.

Эта функция опирается на следующую — добавление номера в скобки на конце Читать далее «Delphi. Алгоритмы. Создание уникального имени через добавление номера в конце в скобках. Например SomeFile(1), SomeFile(2) и др.»

Delphi. Как отсортировать TStringList и сохранить соответствие с несколькими другими TStringList?

Данный пост является развитием предыдущего. Будем сортировать один TStringList -другие же приводить в соответствие с переставленными элементами.

Исходные данные у меня точно такие же. Не буду переписывать часть поста сюда.Изменился только алгоритм сортировки, так как теперь в соответствие нужно привести не один, а несколько списков. Читать далее «Delphi. Как отсортировать TStringList и сохранить соответствие с несколькими другими TStringList?»

Delphi. Сортировка TStringList с приведением в соответствие другого TStringList

Что делаем?

Есть у нас некоторый TStringList, скажем SLToSort:TStringlist. Нужно его отсортировать — задача элементарная, пишем компараторы для наших данных, включаем CustomSort и всё готово. А что делать, если кроме SLToSort есть просто SomeSL:TStringlist и после сортировки SLToSort — нужно привести его элементы в соответствие с SLToSort, ну то есть так….

Где это может понадобиться?

Случай редкий, но всё же. Я делаю небольшой FTP клиент, который собирает данные о файлах на сервере. В принципе — вся информация уже есть и её хранит ОС, я к тому, что в данном случае вопрос использования БД — это действительно вопрос. Я подумал, что логично, просто собирать эти данные и использовать в FTP клиенте, но возникли нюансы, в частности с сортировкой списков. В SQL одна простая инструкция SortBy, а здесь приходится изобретать, но плюс в том, что программа становится независимой от БД.

Мне казалось, что я вроде сделал это, пока не наткнулся на глюк того, что если элементы одинаковые, то алгоритм работает некорректно. Немного последив за тем, как работает встроенный алгоритм CustomSort, на котором я строил свой алгоритм, я понял, что он меняет местами элементы, даже если они одинаковые. В основе CustomSort лежит QuickSort, если немного раскопать внутренности метода. Но суть не в этом.  Читать далее «Delphi. Сортировка TStringList с приведением в соответствие другого TStringList»

Delphi. Делаем простой инкрементальный поиск

Пусть на ListView выведены данные. Сделаем простой инкрементальный поиск…

45

46

Данные будем брать из ListView. Алгоритм поиска самый простой — перебор, при желании и обилия большого числа данных его легко можно заменить, скажем на бинарный поиск. Сначала результаты поиска сохраним в отдельном списке, и далее будем проматывать по мере нажатия кнопки далее, показывая результаты.  Читать далее «Delphi. Делаем простой инкрементальный поиск»

Delphi. Алгоритмы. Как заменить имя файла на уникальное ?

Скажем, у нас есть имя файла в формате Filename.jpg в переменной FileName. Далее код на уровне идеи…

Вариант 1 через GUID

Вот пример такого изменения. Сохраняем часть старого имени для читабельности и добавляем GUID

Вариант 2 через Random

Отделим имя от расширения, в предпоследнем элементе массива заменим имя на уникальное через Random

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

Мне этот алгоритм нравится, но не до конца… Он работает быстро, но сам вид файла, не эстетичен))

Вариант 3 через циклы while / repeat

Читать далее «Delphi. Алгоритмы. Как заменить имя файла на уникальное ?»