Фундаментальные обходыFundamental traversals

BFS посещает граф "слоями": сначала все вершины на расстоянии 1 ребра от старта, потом все на расстоянии 2, и так далее. Реализуется через очередь (FIFO): вершина добавляется в очередь при первом обнаружении, обрабатывается (посещаются её соседи) в порядке добавления. Ключевое следствие этого порядка: когда BFS впервые достигает вершину, найденный путь до неё — гарантированно кратчайший по числу рёбер (не по весу — для взвешенного графа это уже Дейкстра, см. 3.2.1).BFS visits a graph "layer by layer": first every vertex 1 edge away from the start, then every vertex 2 edges away, and so on. It's implemented with a queue (FIFO): a vertex is enqueued the first time it's discovered, and processed (its neighbors are visited) in the order it was enqueued. The key consequence of this order: the first time BFS reaches a vertex, the path found to it is guaranteed to be the shortest by edge count (not by weight — that's Dijkstra for a weighted graph, see 3.2.1).

std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> dist(adj.size(), -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {           // впервые обнаружена — кратчайшая по рёбрам// first discovery — shortest by edge count
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

DFS уходит из текущей вершины в первого непосещённого соседа максимально глубоко, прежде чем вернуться (backtrack) и попробовать следующую ветку. Реализуется через стек — явный, либо неявный через рекурсию (что и есть стек вызовов). В отличие от BFS, DFS не даёт кратчайших путей, зато естественно выявляет структуру графа: порядок входа/выхода из вершины (`tin`/`tout`) — основа алгоритмов поиска мостов, точек сочленения и компонент сильной связности (см. 3.1.3).DFS goes as deep as possible into the first unvisited neighbor before backtracking to try the next branch. It's implemented with a stack — explicit, or implicit via recursion (which is exactly a call stack). Unlike BFS, DFS doesn't give shortest paths, but it naturally exposes the graph's structure: a vertex's entry/exit order (`tin`/`tout`) underlies the algorithms for finding bridges, articulation points, and strongly connected components (see 3.1.3).

void dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v, adj, visited);  // углубляемся до упора// go as deep as possible
    }
}

Классификация рёбер, которую даёт DFS на ориентированном графе, — не академическая формальность, а инструмент: tree edge (ведёт к непосещённой вершине — часть DFS-дерева), back edge (ведёт к предку в текущей рекурсии — наличие back edge означает, что в графе есть цикл), forward edge (ведёт к уже полностью обработанному потомку), cross edge (ведёт в не связанную по предкам часть дерева). Обнаружение цикла в ориентированном графе — это буквально проверка "встретился ли back edge" во время DFS.The edge classification DFS gives on a directed graph isn't academic formality, it's a tool: a tree edge (leads to an unvisited vertex — part of the DFS tree), a back edge (leads to an ancestor in the current recursion — a back edge existing means the graph has a cycle), a forward edge (leads to an already-fully-processed descendant), a cross edge (leads to an unrelated part of the tree). Detecting a cycle in a directed graph is literally checking "was a back edge encountered" during DFS.

Мост (bridge) — ребро, удаление которого увеличивает число компонент связности графа (разрывает единственный путь между двумя частями). Точка сочленения (articulation point / cut vertex) — то же самое, но про вершину. Оба находятся одним проходом DFS с использованием `tin[v]` (время входа в v) и `low[v]` (минимальный tin, достижимый из поддерева v через один back edge) — если для ребра (u,v) верно `low[v] > tin[u]`, поддерево v не может достичь u или выше без этого ребра, значит (u,v) — мост.A bridge is an edge whose removal increases the graph's number of connected components (it breaks the only path between two parts). An articulation point (cut vertex) is the same idea for a vertex. Both are found in a single DFS pass using `tin[v]` (v's entry time) and `low[v]` (the minimum tin reachable from v's subtree via one back edge) — if for edge (u,v) it holds that `low[v] > tin[u]`, v's subtree cannot reach u or above without that edge, meaning (u,v) is a bridge.