14 · КРАТЧАЙШИЙ ПУТЬ

BFS в графах

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

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Очередь

queue := []State{{start, 0}}
for head := 0; head < len(queue); head++ {
    cur := queue[head]
}

Состояние может включать вершину, расстояние, маску и другие параметры.

Уровни

for steps := 0; len(queue) > 0; steps++ {
    size := len(queue)
    // обработать size элементов
}

Уровень очереди равен расстоянию от старта.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Минимум превращений слова

Соседи отличаются одной буквой.

O(n · word² · alphabet) time · O(n) space

solution.go

func ladderLength(begin, end string, words []string) int {
    dict := map[string]bool{}
    for _, w := range words { dict[w] = true }
    queue := []string{begin}
    for steps := 1; len(queue) > 0; steps++ {
        size := len(queue)
        for ; size > 0; size-- {
            word := queue[0]; queue = queue[1:]
            if word == end { return steps }
            b := []byte(word)
            for i, old := range b {
                for ch := byte('a'); ch <= 'z'; ch++ {
                    b[i] = ch; next := string(b)
                    if dict[next] { delete(dict, next); queue = append(queue, next) }
                }
                b[i] = old
            }
        }
    }
    return 0
}

ПРИМЕР РЕШЕНИЯ

Курс возможен?

Топологическая сортировка по входящим степеням.

O(V + E) time · O(V + E) space

solution.go

func canFinish(n int, prerequisites [][]int) bool {
    graph, degree := make([][]int, n), make([]int, n)
    for _, e := range prerequisites { graph[e[1]] = append(graph[e[1]], e[0]); degree[e[0]]++ }
    queue := []int{}
    for v, d := range degree { if d == 0 { queue = append(queue, v) } }
    done := 0
    for head := 0; head < len(queue); head++ {
        v := queue[head]; done++
        for _, next := range graph[v] { degree[next]--; if degree[next] == 0 { queue = append(queue, next) } }
    }
    return done == n
}

ПРИМЕР РЕШЕНИЯ

Гниющие апельсины

Мультистартовый BFS начинает одновременно из всех гнилых клеток.

O(rows · cols) time · O(rows · cols) space

solution.go

func orangesRotting(grid [][]int) int {
    queue := [][2]int{}
    fresh := 0
    for r := range grid { for c, v := range grid[r] {
        if v == 2 { queue = append(queue, [2]int{r,c}) }
        if v == 1 { fresh++ }
    }}
    minutes := 0
    for fresh > 0 && len(queue) > 0 {
        size := len(queue); minutes++
        for ; size > 0; size-- { queue = spread(grid, queue, &fresh) }
    }
    if fresh > 0 { return -1 }
    return minutes
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Все рёбра должны иметь одинаковый вес
Visited относится ко всему состоянию
Рассмотри двунаправленный BFS