Граф и обход в глубину

Что такое граф

Граф — это множествоКоллекция уникальных элементов без порядка: {1, 2, 3}. По-английски set. вершин (узлов), соединённых рёбрами (связями). Графом описывают всё, где есть «связи»: друзья в соцсети, города и дороги между ними, страницы и ссылки в интернете, зависимости между задачами. Дерево, которое вы уже знаете, — это частный случай графа без цикловКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно..

Рёбра бывают ненаправленными (дружба взаимна: если A дружит с B, то B дружит с A) и направленными (подписка в соцсети — в одну сторону). Граф с циклом — это путь, который возвращается в исходную вершину.

Как хранить граф: список смежности

Самый частый способ — списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. смежности: словарьКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict., где ключ — вершина, а значение — список её соседей. Он экономит память, когда рёбер немного (а так почти всегда). Альтернатива — матрица смежности (таблица n×n, где matrix[i][j] = 1, если есть ребро), но она занимает n² памяти и удобна лишь для плотных графов.

Обход в глубину (DFS)

DFS (depth-first search) идёт «вглубь»: от вершины уходит к первому соседу, от него — к его соседу, и так пока есть куда. Упёрся в тупик — возвращается назад и пробует другие ветки. Ключевое отличие от деревьев: в графе бывают циклы, поэтому нужно помнить посещённые вершины в множестве visited, иначе обход зациклится навсегда.

Вернётся 5: из A достижимы все пять вершин, потому что граф связный. Если бы какая-то вершина была изолирована, DFS бы до неё не добрался, и число было бы меньше — так проверяют связность графа.

⚠️ Частые ошибки новичков

Ошибка. Забыть про множество visited. В графе с циклом (A→B→A) обход будет бесконечно прыгать между вершинами, пока не упрётся в RecursionError. В отличие от дерева, где «вниз» вёл лишь один путь, в графе всегда нужно отмечать посещённые. Запустите сломанный код.