Лабораторная работа VIII «Графы: представление, BFS и DFS»
Студент реализует два представления:
матрица смежности и список смежности.
Обязательные алгоритмы:
-
BFS;
-
DFS;
-
восстановление пути;
-
поиск компонент связности;
-
определение достижимости.
Для ориентированного графа — топологическая сортировка как дополнительное или обязательное задание сильной группе.
Пример бизнес-задачи:
-
вершина — подразделение организации;
-
ребро — информационная связь;
-
определить все подразделения, достижимые из заданного;
-
найти минимальное по числу переходов количество посредников между двумя подразделениями.
Студент обязан сравнить память матрицы и списка на плотном и разреженном графе.