В этой главе мы разобрали основы работы с графами — одной из ключевых структур в алгоритмах. Рассмотрели способы представления графа в памяти, их разновидности и области применения, а также освоили базовые алгоритмы: обходы в глубину и ширину, поиск компонент связности и вычисление кратчайших путей.
Теперь вы умеете:
- различать виды графов (направленные, ненаправленные, взвешенные, невзвешенные) и выбирать подходящее представление (список смежности, матрица);
- выполнять обход в глубину и в ширину и понимать, в каких задачах они применимы;
- находить компоненты связности с помощью обходов и отслеживать посещённые вершины;
- использовать алгоритм Дейкстры для поиска кратчайших путей от одной вершины;
- восстанавливать путь на основе массива предков и избегать ошибок в графах с отрицательными рёбрами.
Далее — новая глава, в которой вы узнаете, как придумываются алгоритмы на практике. Мы разберём базовые техники проектирования: от полного перебора всех вариантов до жадных стратегий и пошаговых приближений к решению. Эти приёмы помогут вам научиться строить собственные алгоритмы.
Чтобы добавить в заметки выделенный текст, нажмите Ctrl + E