Алгоритм DFS («Depth-first search» или «Поиск в глубину»). Обход графа в глубину.

Единственным крайним случаем является корень, потому что по умолчанию мы вставляем его перед другими вершинами. Но исправление здесь очень простое — достаточно посмотреть, не было ли на пересечении более одной ветви (если корень удален, то эти поддеревья становятся несовместимыми друг с другом).

Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript

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

Два основных алгоритма для обхода графа — это поиск в глубину (DFS) и поиск в ширину (BFS).

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

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

DFS следует концепции «погружения с головой в глубину». Идея заключается в том, что мы движемся от начальной точки (пункта, места) в определенном направлении (по определенному пути), пока не достигнем конца пути или цели (точки, которую мы ищем). Если мы достигаем конца пути, но это не пункт назначения, мы возвращаемся назад (к точке разветвления пути) и выбираем другой маршрут.

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

Мы находимся в точке «s» и должны найти вершину «t». Используя DFS, мы исследуем один из возможных путей, идем по нему до конца, а если не находим его, то возвращаемся и исследуем другой путь. Это процесс:

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

Мы достигли конца p1, но еще не нашли t, поэтому возвращаемся к s и переходим ко второму пути.

Когда мы достигаем вершины пути p2, которая ближе всего к s, мы видим три возможных направления дальнейшего движения. Поскольку мы уже посетили вершину первого направления, переходим ко второму.

Мы снова достигли конца пути, но не нашли его, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем желаемой вершины «t».

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

Мы следуем этому алгоритму для каждой вершины, которую посещаем.

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

// если это непрерывный список, // например: adj = функция dfs(adj, v, t).>// если от v до t добраться невозможно return false>

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

Анализ DFS

Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла и игнорируем ранее посещенные, время работы составляет O(V + E).

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

BFS следует концепции «широкого обзора с высоты птичьего полета». Вместо того чтобы следовать определенному пути до конца, BFS предполагает, что он будет обращаться к одному соседу за раз. Это означает следующее:

Вместо того чтобы следовать по пути, BFS за одно действие (шаг) посещает ближайшего соседа s, затем соседа соседа и так далее, пока не будет найдено t.

Чем DFS отличается от BFS? Я представляю, что DFS мчится вперед, а BFS не торопится и исследует все за один шаг.

Тогда возникает вопрос: как узнать, каких соседей посетить в первую очередь?

Для этого мы можем использовать концепцию FIFO (first-in-first-out) из очереди. Сначала мы помещаем в очередь ближайший узел, затем его непосещенных соседей, и продолжаем этот процесс до тех пор, пока очередь не опустеет или мы не найдем искомый узел.

// если это непрерывный список // как здесь: adj = функция bfs(adj, s, t).0)>>// если t не обнаружено, значит пункта назначения достичь невозможно return false>

Анализ BFS

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

В очереди каждая вершина обрабатывается до того, как она достигнет места назначения. Это означает, что в худшем случае BFS просматривает все вершины и ребра.

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

Таким образом, время выполнения BFS также равно O(V + E), а поскольку мы используем очередь, которая принимает все узлы, ее пространственная сложность равна O(V).

Пример DFS

Давайте рассмотрим пример работы алгоритма поиска по глубине. Мы используем неориентированный граф с 5 вершинами.

Мы начинаем с вершины 0. Алгоритм DFS начинает с добавления ее в список посещенных вершин и размещения всех соседних вершин в стеке.

Затем мы посещаем верхний элемент стека, т.е. 1, и переходим к соседним узлам. Поскольку мы уже посетили 0, мы посетим 2.

Узел 2 имеет непосещенный соседний узел 4, поэтому мы добавляем его на вершину стека и посещаем его.

После посещения последнего элемента 3, у него не остается непосещенных соседних узлов. На этом первый «проход в глубины» графика завершен.

Псевдокод DFS (рекурсивная реализация)

Псевдокод для DFS показан ниже. Обратите внимание, что в init() мы запускаем функцию DFS на каждом узле. Причина этого в том, что граф может иметь две разные несвязанные части. Чтобы убедиться, что мы покрываем каждый узел, мы также можем запустить алгоритм DFS на каждом узле.

DFS(G, u) u.visited = true for each v ∈ G.Adju if v.visited == false DFS(G,v) init()

Код DFS

Ниже приведен код алгоритма поиска в глубину с примером. Код был упрощен, чтобы мы могли сосредоточиться на алгоритме, а не на других деталях.

#include #include struct nodestruct node* createNode(int v); struct Graph; struct Graph* createGraph(int)- void addEdge(struct Graph*, int, int)- void printGraph(struct Graph*)- void DFS(struct Graph*, int)- int main()void DFS(struct Graph* graph, int vertex)adjListsvertex; struct node* temp = adjList; graph->visitedvertex = 1; printf("Посетили %dvertex; if(graph->", vertex); while(temp!=NULL)temp = temp->next;>>visitedconnectedVertex == 0)vertex = v; newNode->next = NULL; return newNode;>struct node* createNode(int v)numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->struct Graph* createGraph(int vertices)adjListsi = NULL; graph->visitedi = 0;>return graph;>visited = malloc(vertices * sizeof(int)); int i; for (i = 0; inext = graph->adjListssrc; graph->adjListssrc = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjListsdest; graph->adjListsdest = newNode;>void addEdge(struct Graph* graph, int src, int dest)void printGraph(struct Graph* graph)numVertices; v++)", temp->vertex); temp = temp->next;>printf("\n");>>