Графы: представление, BFS и DFS
Графы: список смежности, обход в глубину и в ширину, компоненты связности и кратчайшие пути.
Граф — вершины, соединённые рёбрами: города и дороги, люди и дружбы, состояния и переходы. Огромный пласт задач формулируется на языке графов.
Хранение: список смежности — для каждой вершины список её соседей. Вектор векторов g, где g[v] — соседи вершины v. Матрица смежности n×n подходит только для маленьких n.
Два базовых обхода:
• DFS (в глубину): идём по ребру, пока можем, потом откатываемся. Естественно пишется рекурсией. Применения: компоненты связности, поиск циклов, топологическая сортировка.
• BFS (в ширину): обходим «волнами» через очередь. Даёт кратчайшие расстояния в невзвешенном графе.
DFS: число компонент связности. Введите: 6 3, затем рёбра: 1 2, 2 3, 4 5
В примере вершины {1,2,3}, {4,5} и одинокая {6} — три компоненты.
BFS кладёт стартовую вершину в очередь, затем повторяет: достали вершину — добавили всех непосещённых соседей. Вершины обрабатываются в порядке удаления от старта, поэтому dist считается корректно.
BFS: расстояния от вершины 1. Введите: 5 4, затем рёбра: 1 2, 2 3, 3 4, 1 5
Оба обхода — O(V + E): каждая вершина и каждое ребро обрабатываются один раз.
Грабли, на которые наступают все:
1. Забытая пометка visited — бесконечный цикл.
2. Рекурсивный DFS на цепочке из 10⁵+ вершин может переполнить стек — пишите итеративный вариант со своим стеком или увеличивайте лимит.
3. dist инициализируется -1 («не был»), и это же значение — готовый ответ для недостижимых вершин.
Задание: лабиринт n×m из точек и решёток — найдите кратчайший путь от входа до выхода (BFS по клеткам: соседи — четыре стороны).
Отметьте урок пройденным.