Когда использовать DFS или BFS для решения проблемы с графиком?

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

• Для поиска определенного узла в графе.
• Чтобы найти кратчайшее расстояние от узла до любого другого узла или до каждого другого узла.
• Посчитать все узлы.
• Или могут быть более сложные задачи, которые нам нужно выполнить так, как проблема определяет нас для этого.

Но одно можно сказать точно: нам нужно пройти по графу. Двумя очень известными методами обхода графа/дерева являются алгоритмы поиска в ширину (BFS) и поиска в глубину (DFS).

Основное различие между этими двумя методами заключается в способе исследования узлов во время нашего обхода.

• BFS: пытается исследовать всех соседей, которых он может достичь от текущего узла. Он будет использовать структуру данных очереди.
• DFS: пытается достичь самого дальнего узла от текущего узла и вернуться (возврат) к текущему узлу, чтобы изучить его других соседей. Это будет использовать структуру данных стека.

Решаете, что использовать, BFS или DFS?

Большинство проблем можно решить с помощью BFS или DFS. Это не будет иметь большого значения. Например, рассмотрим очень простой пример, где нам нужно посчитать общее количество городов, соединенных друг с другом. Где в графе узлы представляют города, а ребра представляют дороги между городами.

В такой задаче мы знаем, что нам нужно перейти к каждому узлу, чтобы подсчитать узлы. Таким образом, не имеет значения, используем ли мы BFS или DFS, поскольку с помощью любого из способов мы будем проходить все ребра и узлы графа. Так что в любом случае временная сложность будет O (E + V), где E — общее количество ребер, а V — общее количество узлов.

Но бывают проблемы, когда нам нужно решить, использовать ли DFS или BFS для более быстрого решения. И нет никакого обобщения. Это полностью зависит от постановки задачи. Это зависит от того, что мы пытаемся найти в решении. Нам нужно четко понимать, что наша проблема хочет, чтобы мы нашли. И проблема может не указывать нам напрямую использовать BFS или DFS.

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

Примеры выбора DFS вместо BFS.

Пример 1:

Consider a problem where you are standing at your house and you have multiple ways to go from your house to a grocery store. You are said that every path you choose has one store and is located at the end of every path. You just need to reach any of the stores.

Очевидным методом здесь будет выбор DFS .

Поскольку мы знаем, что можем найти наше решение (продуктовый магазин) на любом из путей, мы можем просто перейти к любому соседу текущего узла, не исследуя всех соседей. Нет необходимости проходить через BFS, так как он без необходимости исследует другие пути, но мы можем найти наше решение, пройдя любой из путей. Кроме того, мы знаем, что наше решение находится дальше всего от начальной точки, поэтому, если мы выберем BFS, нам придется посетить почти все узлы, поскольку мы посещаем все узлы уровня, и мы будем продолжать делать это до конца, где мы находим продуктовый магазин.

Пример 2:

Consider a problem where you need to print all the nodes encountered in any one of the paths starting from node A to node B in the diagram.

Здесь возможны два пути «А -> 4 -> 6 -> В» и «А -> 5 -> 6 -> В». Здесь нам нужно отслеживать один путь, поэтому нет необходимости исследовать все остальные пути с помощью BFS. Кроме того, не каждый путь приведет нас от A к B. Поэтому нам нужно вернуться к текущему узлу, а затем изучить другой путь и посмотреть, приведет ли он нас к B. Необходимость возврата говорит нам, что мы можем думать в направлении DFS.

Примеры выбора BFS вместо DFS.

Пример 1:

Consider an example of a graph representing connected cities through edges. There are a few nodes colored in red that indicates covid affected cities. White-colored nodes indicate healthy cities. You are asked to find out the time the covid virus will take to affect all the non-affected cities if it takes one unit of time to travel from one city to another.

Здесь даже думать о DFS не представляется возможным. Здесь один пострадавший город повлияет на всех своих соседей за одну единицу времени. Вот откуда мы знаем, что нам нужно применить BFS, поскольку нам нужно сначала изучить всех соседей текущего узла. Еще одна веская причина для BFS здесь заключается в том, что оба узла 0 и 11 начнут одновременно влиять на соседние города. Это показывает, что нам требуется параллельная операция на обоих узлах 0 и 11 . Поэтому нам нужно начать обход всех узлов-соседей обоих узлов одновременно. Таким образом, мы можем поместить узлы 0 и 11 в очередь и начать обход параллельно. Для воздействия на все города потребуется 2 единицы времени.

1. В то время = 0 единиц, Затронутые узлы = {0, 11}
2. В момент времени = 1 единица, затронутые узлы = {0, 11, 3, 2, 8, 7, 6, 9}
3. Время = 2 единицы, затронутые узлы = {0, 11, 3, 2, 8, 7, 6, 9, 5, 1, 4, 10}

Пример 2:

Consider the same example of house and grocery stores mentioned in the above section. Suppose now you need to find the nearest grocery store from the house instead of any grocery store. Consider that each edge is of 1 unit distance. Consider the diagram below:

Здесь использование DFS, как и в предыдущем случае, будет невозможно. Если мы используем DFS, то мы будем двигаться по пути, пока не найдем продуктовый магазин. Но как только мы нашли его, мы не уверены, что это продуктовый магазин на кратчайшем расстоянии. Поэтому нам нужно вернуться, чтобы найти продуктовый магазин на других путях, и посмотреть, есть ли какой-либо другой продуктовый магазин на расстоянии меньшем, чем текущий найденный продуктовый магазин. Это заставит нас посетить каждый узел в графе, что, вероятно, не лучший способ сделать это.

Здесь мы можем использовать BFS , так как BFS проходит узлы уровень за уровнем. Сначала проверяем все узлы на расстоянии 1 единицы от дома. Если какой-либо из узлов является продуктовым магазином, то мы можем остановиться, иначе мы увидим следующий уровень, то есть все узлы на расстоянии 2 единицы от дома и так далее. В большинстве случаев это займет меньше времени, так как мы не будем проходить все узлы. Для данного графа мы будем исследовать узлы только до двух уровней, так как на втором уровне мы найдем продуктовый магазин и вернем кратчайшее расстояние равным 2.

Вывод:

У нас не может быть фиксированных правил использования BFS или DFS. Это полностью зависит от проблемы, которую мы пытаемся решить. Но мы можем сделать некоторую общую интуицию.

• Мы предпочитаем использовать BFS, когда знаем, что наше решение может лежать ближе к начальной точке или если граф имеет большую глубину.
• Мы предпочтем использовать поиск в глубину, когда знаем, что наше решение может лежать дальше всего от начальной точки или когда график имеет большую ширину.
• Если у нас есть несколько начальных точек, и задача требует, чтобы мы начали проходить все эти начальные точки параллельно, тогда мы можем думать о BFS, поскольку мы можем поместить все эти начальные точки в очередь и начать сначала исследовать их.
• Обычно рекомендуется использовать BFS, если нам нужно найти кратчайшее расстояние от узла в невзвешенном графе.
• Мы будем использовать DFS в основном в алгоритмах поиска путей для поиска путей между узлами.

Хотя использование BFS или DFS не ограничивается только этими несколькими проблемами. Вы можете найти больше приложений и использование BFS здесь и DFS здесь.