Даба. ‹ЂЃЋђЂ’ЋђЌЂџ ђЂЃЋ’Ђ Ќ е®¦¤Ґ­ЁҐ Є®¬Ї®­Ґ­в бўп§­®бвЁ ­Ґ®аЁҐ­вЁа®ў . Лабораторная работа Нахождение компонент связности неориентированного графа

• Название: Лабораторная работа Нахождение компонент связности неориентированного графа
• Анкор: Даба
• Дата: 06.09.2022
• Размер: 20.64 Kb.
• Имя файла: ‹ЂЃЋђЂ’ЋђЌЂџ ђЂЃЋ’Ђ Ќ 宦¤Ґ­ЁҐ Є®¬Ї®­Ґ­в бўп§­®бвЁ ­Ґ®аЁҐ­вЁа®ў .docx
• Тип: Лабораторная работа; #664522

ЛАБОРАТОРНАЯ РАБОТА № 1.
Нахождение компонент связности неориентированного графа.

Для нахождения компонент связности графа – граф должен быть представлен в виде, из которого мы однозначно можем сказать, с какими вершинами связана произвольно выбранная нами вершина (например, таблица смежности или списки смежности).

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

Алгоритм нахождения компонент связности графа стратегией обхода графа методом поиска в ширину заключается в следующих действиях:

1. 
   Числу компонент связности присваиваем начальное значение равное нулю.
   
2. 
   Выбираем произвольно начальную вершину и помечаем её как пройденную.
   
3. 
   Все вершины связанные с нашей вершиной помечаем как доступные.
   
4. 
   Для каждой из доступных (в предыдущем пункте) вершин производим аналогичные действия, т.е. вновь выбранную вершину помечаем как пройденную, а все связанные с ней вершины как доступные (если они еще не были помечены).
   
5. 
   Продолжаем так выполнять алгоритм для всех вновь доступных вершин, пока все доступные вершины не будут помечены как пройденные.
   
6. 
   Инкриминируем число компонент связности.
   
7. 
   Проверяем: если в графе остались не помеченные вершины то для непомеченных вершин выполняем алгоритм со второго пункта, в противном случае алгоритм закончен.
   

Алгоритм нахождения компонент связности графа стратегией обхода графа методом поиска в глубину заключается в следующих действиях:
1. Числу компонент связности присваиваем начальное значение равное нулю.

2. Выбираем произвольно начальную вершину и помечаем её как доступную.

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

4. Проверяем, если пути от нее к другим непомеченным вершинам, если есть, то первую же такую вершину помечаем как доступную и переходим на нее, иначе помечаем текущую вершину как пройденную и переходим на предыдущую вершину и снова выполняем этот пункт (если возврат происходит в первую вершину, то переходим к пункту три).

Задание.

1. 
   Построить матрицу смежности и инцидентности для заданного графа. Изобразить граф.
   
2. 
   Используя поиск в глубину и поиск в ширину написать программу, определяющую число компонент связности графа. Методы представляются в виде функций.
   
3. 
   Варианты заданий указаны в таблице 1.
   
4. 
   В таблице граф задан списком ребер.
   

Таблица 1.

№	Кол. вершин	Кол. ребер	Задание графа
1.	9	10	(1,2),(1,4),(1,6),(2,3), 2,5),(3,5), (4,5),(4,6),(7,8),(7,9)
2.	6	8	(1,2),(1,4),(1,5),(1,6),(2,3),(3,4), (4,5),(5,6)
3.	8	8	(1,2),(1,3),(2,3),(3,4),(3,5)(4,5), (5,6)(7,8)
4.	8	6	(1,6),(1,8),2,5),(3,6),(3,8),(4,5)
5.	6	10	(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), (3,5),(4,5),(4,6),(5,6)
6.	9	8	(1,2),(1,3),(1,4), (2,3),(2,4),(3,4), (5,6),(6,7),(8,9)
7.	8	7	(1,4),(2,4),(2,6),(3,6),(4,5),(5,6) (7,8)
8.	6	10	(1,2),(1,3),(2,3),(2,4), (2,5),(3,4),(3,5), (4,5),(4,6),(5,6)
9.	8	8	(1,2),(1,3),(1,4),(2,3), (2,4),(3,4), (5,7),(6,8)
10.	6	8	(1,2),(1,4),(2,3), (2,4),(3,4), (3,6),(4,5),(5,6)
11.	8	6	(1,3),(2,3),(3,4),(4,5),(5,6),(7,8)
12.	7	12	(1,2),(1,3),(1,4),(1,6),(2,3), (2,4),(2,6), (2,7),(3,4),(4,5),(5,6),(6,7)
13.	9	10	(1,2),(1,3),(2,3), (3,4),(4,5), (4,6),(3,4),(7,8),(7,9),(8,9)
14.	11	10	(1,2),(2,4),(2,5),(3,4),(4,7), (5,6),(5,7),(7,8),(9,10),(9,11)