Поиск в ширину по существу означает: посещение всех родительских узлов, затем посещение всех дочерних узлов.
В то время как поиск в глубину вначале означает: посещение всехсначала дочерние узлы, пока вы не достигнете конечного узла (узла без дочерних узлов), затем перейдите к следующему родительскому узлу и всем дочерним узлам и продолжайте, пока вы не посетите все узлы.
Здесьу вас есть изображение (взятое из Википедии), которое показывает порядок (представленный в виде дерева), в котором узлы посещаются при поиске в ширину:
Здесь у вас естьсоответствующее изображение для поиска в глубину:
Псевдокод для
Поиск в ширину:
def BFS(G,v):
create a queue Q
enqueue v onto Q
mark v
while Q is not empty:
t = Q.dequeue()
if t is what we are looking for:
return t
for all edges e in G.incidentEdges(t) do:
o = G.opposite(t, e)
if o is not marked:
mark o
enqueue o onto Q
По сути, вы создаетеочередь и добавление всех узлов в нее ... Помните, что очередь - это структура данных "первым пришел-первым обслужена" .
Поиск в глубину:
def DFS(G, v):
label v as explored
for all edges e in G.incidentEdges(v) do:
if edge e is unexplored then:
w = G.opposite(v, e)
if vertex w is unexplored then:
label e as a discovery edge
recursively call DFS(G, w)
else
label e as a back edge
Теперь, для этого, вы в значительной степени устанавливаете взрывкрасный флаг, если вы изучили все из них, то вы выполнили поиск в глубину по порядку.