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

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

 

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

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

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

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

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

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

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

 

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

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

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

 

This entry was posted in Delphi, Алгоритмы. Bookmark the permalink.

Leave a Reply