← Назад к графовым алгоритмам

BFS - поиск в ширину

Поиск кратчайшего пути в невзвешенном графе

🐍 Python
n, m = map(int, input().split())

G = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

s, t = map(int, input().split())
s -= 1
t -= 1

D = [-1] * n
Q = []
Q.append(s)
D[s] = 0

while Q:
    h = Q.pop(0)
    for a in G[h]:
        if D[a] == -1:
            Q.append(a)
            D[a] = D[h] + 1

print(D[t])
⚙️ C++
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> G(n);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    int s, t;
    cin >> s >> t;
    s--; t--;
    
    vector<int> D(n, -1);
    queue<int> Q;
    
    Q.push(s);
    D[s] = 0;
    
    while (!Q.empty()) {
        int h = Q.front();
        Q.pop();
        
        for (int a : G[h]) {
            if (D[a] == -1) {
                Q.push(a);
                D[a] = D[h] + 1;
            }
        }
    }
    
    cout << D[t] << endl;
    
    return 0;
}

Как работает BFS?

BFS (Breadth-First Search / поиск в ширину) — алгоритм обхода графа, который находит кратчайший путь в невзвешенном графе.

BFS работает по принципу волны: сначала обрабатывается стартовая вершина, затем все её соседи, затем соседи соседей и так далее.

Алгоритм использует очередь:

Вершины обрабатываются в порядке увеличения расстояния от старта. Это гарантирует, что когда вершина впервые посещается, найденное расстояние является минимальным.

Каждая вершина обрабатывается ровно один раз, поэтому время работы линейно зависит от суммы количества вершин и рёбер графа.

Временная сложность: O(n + m), где n — количество вершин, m — количество рёбер.

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода:

4 4
1 2
2 3
3 4
1 4
1 4

Здесь:
n=4 (вершины 1,2,3,4)
m=4 (4 ребра)
Ребра: 1-2, 2-3, 3-4, 1-4
Начальная вершина s=1, конечная t=4

Вывод: 1 (кратчайший путь 1→4)

Попробовать BFS онлайн

Введите граф в формате, описанном выше:

Результат появится здесь...