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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Стандартный 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;
}

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

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Поиск_в_ширину&oldid=2845