Поиск остовного дерева в ширину и поиск в глубину

Во многих приложениях нужно в определенном порядке посетить все узлы графа, т. е. построить остовное дерево.

Рассмотрим следующие два общих способа обхода, называемые поиском в ширину (BFS, breadth-first-search) и поиском в глубину (DFS, depth-first-search).

Поиск в ширину, BFS. Выбираем произвольно узел графа G, назовем этот узел V₀ и затем посетим всех соседей V₀ в произвольном порядке, например, это узлы V ₁, V ₂, …, V _i. После посещения всех соседей V ₀ начать обход заново из V ₁ (первого посещенного соседа узла V₀) и посетить все соседние с V ₁ узлы, ска­жем, V ₁₁, V ₁₂,…, V _{1 j}, потом все новые узлы, соседние с V ₂, скажем, V ₂₁, V ₂₂, …, V _{2 k}. Систематически получаем:

Порядок	Соседние узлы
V 0	V 1, V 2, …, V i
V 1	V 11, V 12,…, V 1 j
V 2	V 21, V 22,…, V 2 j
…	…
V 11	V 11 1, V 11 2,…, V 11 j
V 12	V 12 1, V 12 2,…, V 12 j

На рис. 11 можно взять за V ₀ узел V_a, тогда узлы можно посетить в следующем порядке:

V ₀, V_b, V_c, V_d, V_e, V_f,

V₀, V ₁, V ₂, V ₁₁, V₂₁, V_{11 1}.

Рис. 11.

Если взять в качестве V ₀ узел V_b, то можно посетить вершины в порядке

V_b, V_a, V_c, V_d, V_e, V_f,

V ₀, V ₁, V ₂, V ₃, V ₂₁, V ₃₁.

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

Замечание 2. Если пометить дугу, соединяющую посещенный узел с ранее посещенным узлом, то все эти помеченные дуги образуют остовное дерево графа G; если же каждая дуга имеет длину 1, то остовное дерево является деревом кратчайших путей из V₀ во все остальные узлы G.

Поиск в глубину, DFS. Выбираем произвольно вершину V ₀, а затем следуем по ребру е ₀₁ в узел V_i, потом следуем по ребру e ₁₂ в узел V ₂, соседний с V ₁. Вобщем случае, после посещения узла V_i следуем по ребру e_ij в узел V_j, если V_j ранее еще не был посещен. Далее применяем рекурсивно этот процесс к V_j и выбираем ребро e_jk в узел V_k. Если вершина V_j уже была посещена, то возвращаемся в V_i и выбираем другое ребро. Если все ребра, инцидентные V_i, уже выбраны и нельзя найти ни одной новой вершины, то возвращаемся из V_j в предыдущую вершину, за которой идет V_i, и проверяем ей инцидентные ребра.

Если на рис. 11 начать с вершины V_b, то можно посетить узлы в следующем порядке (упорядочение определяется не единственным образом):

V_b, V_c, V_a, V_d, V_e, V_f.

Дуги, следующие в новые вершины, образуют остовное дерево. Это дуги: e_bc, e_ca, e_cd, e_de, e_ef.

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

Алгоритмы BFS и DFS имеют одинаковую сложность для самого неблагоприятого случая. Сложность алгоритма для самого неблагоприятного случая – это приблизительная мера максимального числа действий, требуемых, чтобы выполнить алгоритм. Это функция размера входных данных, которые непосредственно в нашем случае были представлены графом (например, О (n)). Так как алгоритмы имеют одинаковую сложность, то ни один из них не имеет преимуществ перед другим. Тем не менее, для целого ряда специфических графов один алгоритм мог бы производить дерево покрытия эффективнее, чем другой. Например, поиск «по глубине» эффективнее для графа «колеса», а поиск «ширине» для графа «Мальтийский крест».