Mid📖Теория7 min

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

BFS: алгоритм, очередь, кратчайший путь в невзвешенном графе

AlgoGraphs

Поиск в ширину (BFS)

Идея BFS

BFS (Breadth-First Search) обходит граф по уровням: сначала все вершины на расстоянии 1, потом на расстоянии 2 и т.д. Используется очередь.

Граф:
  0 --- 1 --- 3
  |     |
  2 --- 4 --- 5

BFS из 0: 0 -> 1, 2 -> 3, 4 -> 5
Уровень 0: {0}
Уровень 1: {1, 2}
Уровень 2: {3, 4}
Уровень 3: {5}

Базовый алгоритм

PHPGo
<?php
declare(strict_types=1);

/** @return list<int> */
function bfs(array $graph, int $start): array
{
    $visited = [$start => true];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $order = [];

    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $order[] = $node;

        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }

    return $order;
}

func bfs(graph [][]int, start int) []int {
    visited := make(map[int]bool)
    visited[start] = true
    queue := []int{start}
    order := []int{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }

    return order
}
**Сложность:** O(V + E) времени, O(V) памяти.

Кратчайший путь в невзвешенном графе

BFS автоматически находит кратчайший путь (по количеству рёбер) в невзвешенном графе.

PHPGo
<?php
declare(strict_types=1);

/** @return list<int> */
function shortestPath(array $graph, int $start, int $end): array
{
    if ($start === $end) {
        return [$start];
    }

    $visited = [$start => true];
    $queue = new SplQueue();
    $queue->enqueue([$start, [$start]]);

    while (!$queue->isEmpty()) {
        [$node, $path] = $queue->dequeue();

        foreach ($graph[$node] as $neighbor) {
            if ($neighbor === $end) {
                $path[] = $neighbor;
                return $path;
            }
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $newPath = $path;
                $newPath[] = $neighbor;
                $queue->enqueue([$neighbor, $newPath]);
            }
        }
    }

    return []; // Path not found
}

type queueItem struct {
    node int
    path []int
}

func shortestPath(graph [][]int, start, end int) []int {
    if start == end {
        return []int{start}
    }

    visited := make(map[int]bool)
    visited[start] = true
    queue := []queueItem{{start, []int{start}}}

    for len(queue) > 0 {
        item := queue[0]
        queue = queue[1:]

        for _, neighbor := range graph[item.node] {
            if neighbor == end {
                return append(item.path, neighbor)
            }
            if !visited[neighbor] {
                visited[neighbor] = true
                newPath := make([]int, len(item.path)+1)
                copy(newPath, item.path)
                newPath[len(item.path)] = neighbor
                queue = append(queue, queueItem{neighbor, newPath})
            }
        }
    }

    return nil // Path not found
}
Более эффективный вариант (без хранения путей в очереди):
PHPGo
<?php
declare(strict_types=1);

/** @return list<int> */
function shortestPathV2(array $graph, int $start, int $end): array
{
    if ($start === $end) {
        return [$start];
    }

    $visited = [$start => true];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $parent = [$start => null];

    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();

        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $parent[$neighbor] = $node;
                $queue->enqueue($neighbor);

                if ($neighbor === $end) {
                    // Reconstruct path
                    $path = [];
                    $current = $end;
                    while ($current !== null) {
                        $path[] = $current;
                        $current = $parent[$current];
                    }
                    return array_reverse($path);
                }
            }
        }
    }

    return [];
}

func shortestPathV2(graph [][]int, start, end int) []int {
    if start == end {
        return []int{start}
    }

    visited := make(map[int]bool)
    visited[start] = true
    queue := []int{start}
    parent := make(map[int]int)
    parent[start] = -1

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                parent[neighbor] = node
                queue = append(queue, neighbor)

                if neighbor == end {
                    // Reconstruct path
                    path := []int{}
                    for cur := end; cur != -1; cur = parent[cur] {
                        path = append(path, cur)
                    }
                    // Reverse
                    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
                        path[i], path[j] = path[j], path[i]
                    }
                    return path
                }
            }
        }
    }

    return nil
}
## Задача: Number of Islands
PHPGo
<?php
declare(strict_types=1);

/** @param list<list<string>> $grid */
function numIslands(array &$grid): int
{
    if ($grid === []) {
        return 0;
    }

    $rows = count($grid);
    $cols = count($grid[0]);
    $count = 0;
    $dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    $bfs = function (int $r, int $c) use (&$grid, $rows, $cols, $dirs): void {
        $queue = new SplQueue();
        $queue->enqueue([$r, $c]);
        $grid[$r][$c] = '0';

        while (!$queue->isEmpty()) {
            [$row, $col] = $queue->dequeue();

            foreach ($dirs as [$dr, $dc]) {
                $nr = $row + $dr;
                $nc = $col + $dc;
                if ($nr >= 0 && $nr < $rows && $nc >= 0 && $nc < $cols && $grid[$nr][$nc] === '1') {
                    $grid[$nr][$nc] = '0';
                    $queue->enqueue([$nr, $nc]);
                }
            }
        }
    };

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($grid[$r][$c] === '1') {
                $bfs($r, $c);
                $count++;
            }
        }
    }

    return $count;
}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows, cols := len(grid), len(grid[0])
    count := 0
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    bfs := func(r, c int) {
        queue := [][2]int{{r, c}}
        grid[r][c] = '0'

        for len(queue) > 0 {
            cell := queue[0]
            queue = queue[1:]

            for _, d := range dirs {
                nr, nc := cell[0]+d[0], cell[1]+d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0'
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                bfs(r, c)
                count++
            }
        }
    }

    return count
}
## Задача: Rotten Oranges (Multi-source BFS)
PHPGo
<?php
declare(strict_types=1);

/** @param list<list<int>> $grid */
function orangesRotting(array &$grid): int
{
    $rows = count($grid);
    $cols = count($grid[0]);
    $queue = new SplQueue();
    $fresh = 0;

    // Initialization: all rotten into queue
    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($grid[$r][$c] === 2) {
                $queue->enqueue([$r, $c]);
            } elseif ($grid[$r][$c] === 1) {
                $fresh++;
            }
        }
    }

    if ($fresh === 0) {
        return 0;
    }

    $minutes = 0;
    $dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    while (!$queue->isEmpty()) {
        $minutes++;
        $levelSize = $queue->count();

        for ($i = 0; $i < $levelSize; $i++) {
            [$r, $c] = $queue->dequeue();

            foreach ($dirs as [$dr, $dc]) {
                $nr = $r + $dr;
                $nc = $c + $dc;
                if ($nr >= 0 && $nr < $rows && $nc >= 0 && $nc < $cols && $grid[$nr][$nc] === 1) {
                    $grid[$nr][$nc] = 2;
                    $fresh--;
                    $queue->enqueue([$nr, $nc]);
                }
            }
        }
    }

    return $fresh === 0 ? $minutes - 1 : -1;
}

func orangesRotting(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    queue := [][2]int{}
    fresh := 0

    // Initialization: all rotten into queue
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 2 {
                queue = append(queue, [2]int{r, c})
            } else if grid[r][c] == 1 {
                fresh++
            }
        }
    }

    if fresh == 0 {
        return 0
    }

    minutes := 0
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    for len(queue) > 0 {
        minutes++
        levelSize := len(queue)

        for i := 0; i < levelSize; i++ {
            cell := queue[0]
            queue = queue[1:]

            for _, d := range dirs {
                nr, nc := cell[0]+d[0], cell[1]+d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                    grid[nr][nc] = 2
                    fresh--
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
    }

    if fresh == 0 {
        return minutes - 1
    }
    return -1
}
## Задача: Word Ladder
PHPGo
<?php
declare(strict_types=1);

/** @param list<string> $wordList */
function ladderLength(string $beginWord, string $endWord, array $wordList): int
{
    $wordSet = array_flip($wordList);
    if (!isset($wordSet[$endWord])) {
        return 0;
    }

    $queue = new SplQueue();
    $queue->enqueue([$beginWord, 1]);
    $visited = [$beginWord => true];

    while (!$queue->isEmpty()) {
        [$word, $length] = $queue->dequeue();

        for ($i = 0, $len = strlen($word); $i < $len; $i++) {
            for ($c = ord('a'); $c <= ord('z'); $c++) {
                $newWord = substr($word, 0, $i) . chr($c) . substr($word, $i + 1);

                if ($newWord === $endWord) {
                    return $length + 1;
                }

                if (isset($wordSet[$newWord]) && !isset($visited[$newWord])) {
                    $visited[$newWord] = true;
                    $queue->enqueue([$newWord, $length + 1]);
                }
            }
        }
    }

    return 0;
}

// "hit" -> "hot" -> "dot" -> "dog" -> "cog"
// Answer: 5

func ladderLength(beginWord, endWord string, wordList []string) int {
    wordSet := make(map[string]bool, len(wordList))
    for _, w := range wordList {
        wordSet[w] = true
    }
    if !wordSet[endWord] {
        return 0
    }

    type item struct {
        word   string
        length int
    }

    queue := []item{{beginWord, 1}}
    visited := map[string]bool{beginWord: true}

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]

        wordBytes := []byte(cur.word)
        for i := 0; i < len(wordBytes); i++ {
            orig := wordBytes[i]
            for c := byte('a'); c <= byte('z'); c++ {
                wordBytes[i] = c
                newWord := string(wordBytes)

                if newWord == endWord {
                    return cur.length + 1
                }

                if wordSet[newWord] && !visited[newWord] {
                    visited[newWord] = true
                    queue = append(queue, item{newWord, cur.length + 1})
                }
            }
            wordBytes[i] = orig
        }
    }

    return 0
}

// "hit" -> "hot" -> "dot" -> "dog" -> "cog"
// Answer: 5
## BFS по уровням (Level BFS)
PHPGo
<?php
declare(strict_types=1);

function bfsByLevel(array $graph, int $start): void
{
    $visited = [$start => true];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $level = 0;

    while (!$queue->isEmpty()) {
        echo "Level {$level}: ";
        $levelSize = $queue->count();

        for ($i = 0; $i < $levelSize; $i++) {
            $node = $queue->dequeue();
            echo "{$node} ";

            foreach ($graph[$node] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $visited[$neighbor] = true;
                    $queue->enqueue($neighbor);
                }
            }
        }

        echo PHP_EOL;
        $level++;
    }
}

func bfsByLevel(graph [][]int, start int) {
    visited := map[int]bool{start: true}
    queue := []int{start}
    level := 0

    for len(queue) > 0 {
        fmt.Printf("Level %d: ", level)
        levelSize := len(queue)

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            fmt.Printf("%d ", node)

            for _, neighbor := range graph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }

        fmt.Println()
        level++
    }
}
## Когда использовать BFS
Задача Почему BFS
Кратчайший путь (невзвешенный) Гарантирует минимум
Обход по уровням Естественный обход
Ближайший объект Первый найденный = ближайший
Multi-source BFS Старт из нескольких источников
Проверка двудольности По уровням раскрашиваем

Запомни: BFS = очередь + visited. Гарантирует кратчайший путь в невзвешенном графе. Multi-source BFS — кладём все стартовые вершины в очередь сразу. Для матричных задач (islands, rotten oranges) — обходи 4 направления. Сложность всегда O(V + E).

Итоги

  1. BFS: очередь, обход по уровням
  2. Кратчайший путь в невзвешенном графе
  3. Сложность: O(V + E)
  4. Multi-source BFS: несколько стартов одновременно
  5. Матричные задачи: 4 направления, проверка границ

Проверь себя

🧪

Что выведет BFS по уровням для графа, если стартовая вершина 0? ``` Граф: 0-1, 0-2, 1-3, 2-3, 3-4 ```

🧪

Почему BFS гарантирует кратчайший путь в невзвешенном графе, но НЕ гарантирует во взвешенном?

🧪

Какова временная и пространственная сложность BFS для графа с V вершинами и E рёбрами?

🧪

В задаче Rotten Oranges (гниющие апельсины) используется multi-source BFS. Что это значит?

🧪

Какую структуру данных использует BFS для обхода графа?

Связанные темы

Поиск в глубину DFS

Связанная тема

Алгоритм Дейкстры

Связанная тема

Паттерны с HashMap

Связанная тема

Быстрая сортировка

Связанная тема