Сигнал задачи
Когда применять
Сущности соединены произвольными отношениями или переходами.
Что держать в голове
- Уметь строить список смежности для ориентированного и неориентированного графа.
- Уметь видеть сетку как неявный граф без явного хранения всех рёбер.
Сложность
- DFS и BFS по спискам смежности: O(V + E) времени и O(V) дополнительной памяти, не считая хранения графа.
Границы и ошибки
- В ориентированном и неориентированном графах рёбра добавляются по-разному; visited отмечают в момент обнаружения, чтобы не раздувать очередь.