Урок 14: Графы — BFS и DFS

Представьте карту городов, соединённых дорогами, или друзей в социальной сети. Всё, что представляет собой «точки и отношения между ними», — это «граф»: узлы (nodes), соединённые рёбрами (edges). Есть два способа обойти граф: BFS расходится кольцо за кольцом, как круги по воде, — отлично подходит дл

BFS — это как круги на воде: вы начинаете в одной точке и расходитесь кольцо за кольцом, сначала к ближайшим. DFS — это как ходьба по лабиринту: вы идёте до конца по одному пути, а если застреваете — возвращаетесь назад и пробуете другой.

обход графа: Систематическое посещение каждого узла, достижимого из начального узла, с помощью BFS (очередь) или DFS (стек/рекурсия).
словарь смежности: Представление графа, в котором каждый узел сопоставлен со списком своих соседей: {node: [neighbors]} — доступ к соседям за O(1).
множество посещённых: Множество (set), отмечающее, какие узлы уже просканированы, чтобы не посещать их снова и избежать бесконечных циклов.