Поиск в ширину

Стандартный BFS

vector<int> bfs(vector<vector<int>> &graph, int start) {
    vector<int> dist(graph.size(), 1e9);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : graph[v]) {
            if (dist[to] > dist[v] + 1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }

    return dist;
}

BFS на неявном графе

vector<vector<int>> bfs(vector<vector<int>> &a, int startY, int startX) {
    vector<vector<int>> dist(a.size(), vector<int>(a[0].size(), 1e9));
    queue<pair<int, int>> q;
    
    dist[startY][startX] = 0;
    q.push({ startY, startX });
    
    vector<int> dy = { -1, 0, 1, 0 };
    vector<int> dx = { 0, 1, 0, -1 };
    
    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
            
        for (int d = 0; d < dy.size(); d++) {
            int ty = y + dy[d];
            int tx = x + dx[d];
            
            if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && dist[ty][tx] > dist[y][x] + 1) {
                dist[ty][tx] = dist[y][x] + 1;
                q.push({ ty, tx });
            }
        }
    }
    
    return dist;
}

Ссылки на задачи

• ACMP #127 — Путь
• ACMP #128 — Один конь
• ACMP #129 — Табличка (BFS одновременно от всех единичных вершин)
• ACMP #130 — Два коня
• ACMP #238 — Побег с космической станции
• ACMP #308 — Вода
• ACMP #381 — Lines
• ACMP #426 — Lines - 2
• ACMP #431 — Путь коня
• ACMP #509 — Игра Jammed
• ACMP #695 — Мифические шахматы
• Codeforces #100082.C — Обход в ширину

Ссылки

• e-maxx.ru — Поиск в ширину
• neerc.ifmo.ru/wiki — Обход в ширину
• brestprog.neocities.org — Обход в ширину (BFS)
• algorithmica.org — Поиск в ширину
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3
• algs4.cs.princeton.edu/lectures — 4.1 Undirected Graphs
• Brilliant.org — Breadth-First Search
• VisuAlgo — Single-Source Shortest Paths