10. Графы

Задачи

ВИДЕО РАЗБОР - смотреть перед лекцией!

2-D ДП (похожие на графы)

• 62. Unique Paths РЕШЕНИЕ

• 63. Unique Paths II РЕШЕНИЕ

• 64. Minimum Path Sum РЕШЕНИЕ

Графы

• 207. Course Schedule РЕШЕНИЕ

• 210. Course Schedule II РЕШЕНИЕ_DFS

• 200. Number of Islands РЕШЕНИЕ_BFS #яндекс ВИДЕО РАЗБОР

• 130. Surrounded Regions РЕШЕНИЕ_DFS РЕШЕНИЕ_BFS

• 695. Max Area of Island РЕШЕНИЕ_DFS

• 1091. Shortest Path in Binary Matrix РЕШЕНИЕ

Доп. вопросы

• Вопрос: Какие есть способы хранения графа?

• Вопрос: Что такое связная компонента графа?

• Вопрос: Что такое цикл в графе? Как можно проверить, что в графе есть цикл?

• Вопрос: Чем отличается dfs от bfs? Приведите пример, когда можно использовать bfs, а когда dfs

• Вопрос: Можно ли использовать bfs/dfs для поиска цикла?

• Вопрос: Для чего нужна топологическая сортировка и что это такое?

• Вопрос: Когда нельзя сделать топологическую сортировку?

• Вопрос: Можно ли использовать bfs/dfs для поиска кратчайшего пути?