Поиск в ширину: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">4iDv8Zu8L3I</youtube>
<youtube width="300" height="180">jqtCPow_iGY</youtube>
<youtube width="300" height="180">xGvIoExlqIw</youtube>
== Стандартный 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;
}
== Ссылки на задачи ==
== Ссылки на задачи ==
* [http://acmp.ru/?main=task&id_task=127 ACMP #127 &mdash; Путь]
* [http://acmp.ru/?main=task&id_task=127 ACMP #127 &mdash; Путь]
Строка 16: Строка 73:
* [http://e-maxx.ru/algo/bfs e-maxx.ru &mdash; Поиск в ширину]
* [http://e-maxx.ru/algo/bfs e-maxx.ru &mdash; Поиск в ширину]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki &mdash; Обход в ширину]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki &mdash; Обход в ширину]
* [http://brestprog.neocities.org/lections/bfs.html brestprog.neocities.org &mdash; Обход в ширину (BFS)]
* [http://algorithmica.org/tg/bfs algorithmica.org — Поиск в ширину]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 3]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 3]
* [http://algs4.cs.princeton.edu/lectures/41UndirectedGraphs.pdf algs4.cs.princeton.edu/lectures &mdash; 4.1 Undirected Graphs]
* [http://algs4.cs.princeton.edu/lectures/41UndirectedGraphs.pdf algs4.cs.princeton.edu/lectures &mdash; 4.1 Undirected Graphs]
* [http://brilliant.org/wiki/breadth-first-search-bfs Brilliant.org — Breadth-First Search]
* [http://visualgo.net/sssp.html VisuAlgo &mdash; Single-Source Shortest Paths]
* [http://visualgo.net/sssp.html VisuAlgo &mdash; Single-Source Shortest Paths]


[[Category:Кратчайшие пути из одной вершины]]
[[Category:Кратчайшие пути из одной вершины]]

Текущая версия от 15:25, 24 мая 2023

TLDR

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

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

Ссылки