Курсовая работа: Определение связности графа на Лиспе

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

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

2 Обоснование выбора алгоритма и структур данных

Для определения связности графа используется поиск пути от одной вершины к другой. Граф является связным, если все вершины связаны между собой. Можно утверждать, что граф является связным, если одну из вершин можно соединить со всеми другими путем. Алгоритм определения связности графа заключается в поиске пути от первой вершины ко всем остальным. Если все пути можно найти – значит граф связный.

Поиск пути от одной вершины к другой будет выполняться по алгоритму поиска в ширину. Схема алгоритма изображена на рисунке 2.1.

Рис.2.1 – Схема алгоритма поиска в ширину

Поиск вершин, смежных с новыми вершинами выполняется так:

а) Если список ребер пустой – выход.

б) Берется первое ребро в списке ребер.

в) Если одна из вершин ребра находится в списке новых вершин, а вторая не входит ни в список новых вершин, ни в список найденных вершин, то вершина добавляется в список смежных вершин.

г) Удалить из списка ребер первое ребро и перейти к пункту а.

Граф представляется двумя множествами (списками): списком вершин и списком ребер. Каждое ребро – это список из двух вершин. Данный выбор обосновывается тем, что списки являются основным способом представления множеств данных.

3 Описание алгоритма

Были разработаны следующие функции (текст программы приведен в приложении 1).

Функция smezver(xysnaidsnov) – определяет, является ли вершина y смежной с одной из новых вершин (x – входит в список новых вершин, y – не входит в списки новых и найденных вершин).

Параметры:

- x - первая вершина ребра;

- y - вторая вершина ребра;

- snaid - список найденных вершин;

- snov - список новых вершин.

Функция smez(snaidsnovsreb) - поиск смежных с новыми вершинами вершин.

Параметры:

- snaid - список найденных вершин;

- snov - список новых вершин;

- sreb - список ребер.

Функция shir(snaid snov y sreb) - поиск в ширину пути.

Параметры:

- snaid - список найденных вершин;