Краткие итоги

1. Графы являются моделью представления данных, основанных на отношениях между элементами множеств.

2. Для представления графов используется несколько способов: список ребер, матрица смежности, матрица инцидентности.

3. Для организации поиска на графах используются обходы в глубину и в ширину.

4. Реализацию обходов можно осуществлять рекурсивными и нерекурсивными алгоритмами.

5. От вида графа и способа его представления зависит временная сложность выполнения алгоритма.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

1. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину.

2. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину.

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

4. Перенумеруйте вершины графа в порядке обхода в глубину и вычислите среднюю плотность графа как частное от деления количества его ребер на число вершин. Можно ли оба эти действия выполнить за один обход графа?

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

Контрольные вопросы

1. Как связаны между собой различные способы представления графов?

2. Как от вида или представления графа зависит временная сложность алгоритмов поиска в глубину и в ширину?

3. Как при реализации в коде выполняется возвращение из тупиковых вершин при обходе графа?

4. Как выполняется обход в несвязном графе?

5. Распространяются ли понятия "поиск в глубину" и "поиск в ширину" на несвязный граф? Ответ обоснуйте.

6. Охарактеризуйте трудоемкость рекурсивного и нерекурсивного алгоритмов обхода графа.