Как пройти по графику, используя поиск в ширину и поиск в глубину

Краткое объяснение двух самых популярных алгоритмов поиска в теории графов

Большинство читателей, наверное, уже в какой-то мере знакомы с тем, что такое графы, но тем не менее давайте установим точки соприкосновения.

Что такое график?

Вероятно, самое простое и расплывчатое определение графа состоит в том, что это структура данных, представляющая упорядоченную пару G = (V, E), где «V» обозначает набор вершин (часто называемых «узлами»),а «E» обозначает набор ребер (обычно называемых ссылками или соединениями). Другими словами, вершины — это элементы графа, а ребра — связи между ними.

Можно думать о графе как о карте, которая представляет несколько городов, соединенных шоссе. Вершины — это города на карте, а дороги, соединяющие города, — это ребра. Другим популярным представлением графа является своего рода социальная сеть. Независимо от того, говорим ли мы о платформе социальных сетей или реальной жизни, люди так или иначе социально взаимосвязаны. Эти соединения также могут быть представлены в виде ребер и вершин графа.

Типы графиков

• Взвешенные графики:

A weighted graph is a graph in which some value(the weight)is assigned to each edge. Those weights can represent expenses, lengths or capacities, depending on the context of the given problem. In unweighted graph a constant value n is assigned to all edges.

• Ориентированные графы

We call a graph directed when its edges have directions. Meaning the edges point to vertices. The graph can be traversed only by following the direction of the edges. In an undirected graph the edges have no directions. Thus each edge can be traversed in both directions.

• Ациклические графы

An acyclic graph is a graph that has no cycles. It means that starting at a random vertex it is impossible to return to the same vertex when traversing the graph.

Обход графа?

По сути, обход графа означает посещение каждой вершины этого графа. Этот процесс может оказаться полезным для перебора файловой системы, элементов DOM, социальных связей, топологических объектов или при работе с любой сущностью, которую можно представить в виде графа.

(Имейте в виду, что модель DOM – это дерево, тип графа. Дерево – это неориентированный, связный, ациклический граф).

Все идет нормально. Давайте, наконец, посмотрим, как работают эти сочные алгоритмы. Сначала я буду использовать более абстрактный подход, не вдаваясь в подробности реализации.

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

Начнем с выбора произвольной вершины в некотором графе. Это будет наша корневая вершина. Мы помечаем нашу корневую вершину как проверенную, а затем переходим к одному из соседей нашего корня. Важно пометить узлы как проверенные после того, как мы их посетили, чтобы мы знали, где мы уже были. Теперь сосед становится корневой вершиной, его тоже помечаем как проверенный и повторяем процесс… переходим к его соседу и так далее, и так далее, пока не дойдем до конца текущей ветки. Когда это происходит, мы возвращаемся к последней вершине, у которой были параметры, отличные от тех, которые мы выбрали в прошлый раз, и повторяем процесс, пока не проверим все узлы.

Этот алгоритм будет в основном проходить по графу в глубину, ветвь за ветвью. Наш приоритет — идти как можно глубже, прежде чем вернуться назад.

Псевдокод для DFS:

dfs(currentNode, graph, visited, exploredNodes):
   if( visited does not contain currentNode):
      visited.add(currentNode)
      exploredNodes.offer(currentNode)

      if ( currentNode is in graph):
       for (childNode in graph.get(currentNode))
         dfs(childNode)

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

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

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

Псевдокод для BFS:

bfs(node, graph, visited, exploredNodes):
    if( visited does not contain node):
       queue = new Deque()
       visited.add(node)
       queue.offer(node)
       exploredNodes.offer(node)
       while queue is not empty:
         currentNode = queue.poll()
         
         if ( currentNode is in graph):
             for (childNode in graph.get(currentNode)):
                if( visited does not contain childNode):
                   visited.add(childNode)
                   exploredNodes.offer(childNode)
                   queue.offer(childNode)

Применение

Излишне говорить, что нет «лучшего», когда речь идет о DFS и BFS. Оба они полезны в разных ситуациях, поэтому выбор алгоритма полностью зависит от конкретной проблемы. Вот несколько примеров, которые могут пролить свет на эту тему. Однако считайте эти примеры просто эмпирическим правилом, скорее всего, вам придется поэкспериментировать, пока вы не найдете решение, которое лучше всего подходит для вашей проблемы.

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

DFS может быть более практичным, когда мы имеем дело со слишком широким графом или когда у нас есть много решений, но они расположены глубоко в графе. DFS может оказаться полезным при реализации игр, в которых каждое принятое решение ведет к новым возможностям. Шахматы например.

Кратчайший путь в графе

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

Давайте посмотрим на следующий пример:

Если мы решим использовать DFS и нам очень повезет, мы сможем найти O только после проверки двух узлов. Это наилучший сценарий, однако он не гарантирован. В этом примере O также может быть последним узлом, который проверяет DFS. Другими словами, мы можем быть уверены, что DFS достигнет конечного пункта назначения, но мы не можем быть уверены, что это будет сделано кратчайшим возможным путем.

Естественно, можно полагаться исключительно на случай, надеясь, что DFS приведет к лучшему сценарию, но это крайне маловероятно. Как мы уже говорили, в этом конкретном случае лучший сценарий для поиска O для DFS — это проверка двух узлов. Тем не менее, в этом примере в худшем случае для DFS будет проверяться 12 узлов, причем O будет последним. Поэтому я считаю, что можно с уверенностью сказать, что средняя производительность DFS в этом случае составляет 7 узлов до достижения пункта назначения.

Для BFS наилучшим сценарием было бы найти O после проверки 4 узлов. Однако в худшем случае будет найдено O после проверки 7 узлов. В среднем BFS найдет O в этом графе после прохождения 5,5 узлов.

Да, BFS в среднем работает лучше, но кто-то может сказать, что разница незначительна. Это было бы верно для данного конкретного случая, но помните, что вы можете иметь дело с огромным графом с сотнями или тысячами узлов. В этом случае BFS заметно превзойдет DFS.

Псевдокод для поиска кратчайшего пути с помощью BFS:

bfs(graph, startingNode, destinationNode, visited, path:
    queue = new Deque()
    visited.add(node)
    queue.offer(node)
    path.add(node)
    while queue is not empty:
       currentNode = queue.poll()
       if (currentNode == destinationNode) return;
         
       if ( currentNode is in graph):
          for (childNode in graph.get(currentNode)):
             if( visited does not contain childNode):
                visited.add(childNode)
                path.offer(childNode)
                if (childNode == destinationNode) return
                queue.offer(childNode)

Единственное отличие состоит в том, что мы проверяем, достигли ли мы узла назначения, и если да, то возвращаемся из BFS. Узлы, которые мы прошли, прежде чем достичь пункта назначения, хранятся в нашем списке путей.

Выполнение

Примеры для DFS и BFS будут в java. Имейте в виду, что эти алгоритмы могут быть реализованы по-разному и с разными типами данных. Это просто примеры для тестирования и отладки. Вы можете изменить способ чтения графика или способ его представления. Однако в этом примере я представлю график как карту. Ключом на этой карте может быть любой узел, а значениями будет список со всеми соседними дочерними узлами текущего узла. Внизу вы можете найти тестовый ввод, представляющий график на рисунках выше.

ДФС

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

БФС

Поиск в ширину обычно реализуется с использованием очереди.

Тестовый ввод