Заключение¶
В этой главе мы рассмотрели абстрактный тип данных для графа и несколько его реализаций. Такая структура данных позволяет решать множество задач, если получается преобразовать оригинальную проблему во что-то, что можно представить в виде графа. В частности, мы увидели, что графы полезны при решении задач из следующих областей:
- Поиск в ширину для нахождения невзвешенного кратчайшего пути.
- Алгоритм Дейкстры для взвешенного кратчайшего пути.
- Поиск в глубину для исследования графа.
- Сильно связные компонеты для упрощения графа.
- Топологическая сортировка для упорядочения заданий.
- Минимальное взвешенное островное дерево для вещания сообщений.