Графы и обходы

Граф $G = (V, E)$ — это множество вершин $V$ и множество рёбер $E$, соединяющих пары вершин. В неориентированном графе ребро $\{u, v\}$ не имеет направления; в ориентированном — есть дуга $u \to v$.

Два базовых обхода:

• BFS (breadth-first search) — в ширину: сначала все соседи, потом соседи соседей. Даёт кратчайшие пути по числу рёбер.
• DFS (depth-first search) — в глубину: идём по ветке до конца, затем откатываемся.

Ниже — случайный граф Эрдёша–Реньи $G(n, p)$: можно менять число вершин и вероятность ребра, выбрать старт (или кликнуть по вершине) и пройти BFS/DFS по шагам.

Разбор на Python (networkx)

Тот же сюжет в коде: строим граф, считаем BFS-дерево и рисуем его.