Delphi. Алгоритмы. Создание графа на списках смежности

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

Основная идея графа на списках смежности как я понял для себя ещё раз) – сделать массив списков смежности. Описывая граф, мы смотрим, связана ли его вершина с другими вершинами, если да, то создаем список смежности, скажем 1 вершина связана с 5 и 7, значит, можем создать такой список из 3 элементов, в котором из 1 вершины будет ссылка на 5, из 5 на 7, либо в другом порядке, но важно, что мы перечислили все вершины, с которыми смежна наша 1 вершина. Таким макаром проходим по всем другим вершинам, должно получиться что-то вроде…

Теория хорошо описана здесь.

Так как была ночь и я устал, бахаю весь модуль…

Ну и исходнички  412_Graph

Чуть позже на форуме дали более простой и элегантный способ сделать тоже самое

Заводим список вершин и ребер

Добавляем пару вершин и ребро, которое их соединяет

Уничтожаем

 

 

This entry was posted in Delphi. Bookmark the permalink.

Leave a Reply