Понимание сложности пространства - решение BFS - Рисование булевой матрицы

Question

Я пытаюсь понять пространственную сложность решения BFS для рисования проблемы булевой матрицы в «Элементах интервью программирования». Это похоже на проблему заполнения потока (проблема 733) в Leetcode.

Решение выглядит следующим образом. Я могу добавить текущий элемент, который нуждается в изменении в очередь. Любые смежные (сверху / снизу / вверх / вниз) узлы также нуждаются в изменении. Поэтому я добавляю их в очередь (если они удовлетворяют критериям, которые будут добавлены в очередь. Всякий раз, когда обрабатывается элемент из очереди, добавляются смежные элементы. Мы будем выполнять обработку до тех пор, пока очередь не станет пустой.

Я думал, что сложность пространства (наихудший случай) будет O (MN), потому что все элементы также могут быть в очереди.Но в книге упоминается, что сложность пространства наихудшего случая равна O (M + N), так как есть не более O (M + N) записей на заданном расстоянии от узла. Я понимаю, что элементы также постоянно удаляются из очереди. Даже тогда мне трудно представить, как они достигают этой сложности пространства. Может кто-то пожалуйста, помогите мне понять?

Answer 1

Ключом к этому является то, что BFS посещает узлы в порядке их расстояния от начального узла. Это то, что делает BFS подходящим для поиска кратчайших путей в невзвешенных графиках.

В любой момент времени очередь не может содержать два узла u и v, таких как distance(start, u) и distance(start, v) отличаются более чем на 1. Предположим, что расстояние u от начального узла равно 3, а v равно 5:

• Если v происходит до u в очереди, затем мы посещаем его до u - противоречие, потому что BFS посещает узлы на более ранних расстояниях до узлов на больших расстояниях.
• Если u встречается раньше v в очереди, затем при посещении u мы добавим соседей u в очередь. Эти соседи находятся на расстоянии 4 от начального узла, но теперь они находятся после v в очереди, поэтому v будут посещаться до них, несмотря на то, что расстояние больше 4 - еще одно противоречие.

Таким образом, всегда существует некоторое расстояние d, такое, что очередь содержит только узлы на расстоянии d или расстоянии d + 1, и, кроме того, все узлы на расстоянии d встречаются до того, как узлы на расстоянии d + 1 в очереди. Это l oop инвариант алгоритма BFS.

---

Предположим, вы выполняете BFS в сетке M-by-N, где каждый узел связан со всеми своими ортогональные соседи. Тогда для любого d > 0 число узлов на расстоянии d от начала составляет самое большее 4*d, поэтому максимально возможный размер очереди составляет 4*d + 4*(d + 1). Кроме того, максимальное расстояние между любыми двумя узлами составляет M + N - 1. Следовательно, O (M + N) - это асимптотика c, ограниченная размером очереди в любое время.

В случае, когда некоторые узлы сетки «отсутствуют» (т. Е. Неправильный цвет для область, заполненная паводком), максимальное расстояние составляет O (MN), а не O (M + N); так что этот случай значительно сложнее. Интуиция заключается в том, что если у графа более длинные пути, то у него меньше «широко открытого» пространства для путей, по которым они разветвляются, что приводит к меньшей очереди. В крайнем случае, граф может быть одним длинным путем, но в этом случае размер очереди равен O (1).

Однако, есть некоторые графики, где граница 4*d нарушена и, следовательно, очередь может быть больше. Например, можно построить графики в форме ниже, где размер графика равен O (2 ^k ), но размер очереди достигает O (3 ^k ), поэтому сложность пространства BFS - это Θ ((M + N) ^{log ₂ 3} ) на этом семействе графиков. Таким образом, указанная сложность пространства O (M + N) не выполняется в худшем случае, но, вероятно, имеет место в среднем случае.

Это изображение был сделан Heap Overflow (опубликовано в комментариях); начальный узел выделен желтым, а узлы красного цвета будут одновременно находиться в очереди.