Ввод / вывод поиска по ширине в сравнении с поиском по глубине

Question

Мой вопрос не совсем о механизме поиска. Я чувствую, что это намного более обыденно - я не понимаю ни ввода, ни вывода. В частности, в CLRS BFS принимает в качестве входных данных граф и исходный узел, а DFS принимает только граф. Разве DFS не важно, где вы будете искать?

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

Надеюсь, я понимаю. Спасибо!

Редактировать: вот что я имею в виду, когда DFS не берет исходный узел. Это псевдокод DFS от CLRS. Я не вижу, чтобы он брал исходный узел где-либо. Все, что я вижу, это проходит ВСЕ узлы на графике.

DFS(G)
1 for each vertex u ∈ V[G]
2 do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 for each vertex u ∈ V[G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)

DFS-VISIT(u)
1 color[u] ← GRAY ✄ White vertex u has just been discovered.
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] ✄ Explore edge (u,v).
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] ← BLACK ✄ Blacken u;it is finished.
9 f [u] ← time ← time+1

Answer 1

Вводная путаница:

Конкретная DFS, предоставленная CLRS, не заботится о том, где вы ищете. Точный результат поиска будет зависеть от порядка расположения узлов в V[G]. Обычно я думаю, что DFS начинается с узла, например ::1004

DFS-Simple(G, s)
1 for each vertex u ∈ V[G]
2   do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 DFS-VISIT(s)

Версия CLRS создает лес (по одному дереву для каждого компонента графа) вместо одного дерева, которое, по-видимому, лучше соответствует их назначению.

Выходная путаница:

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

Print-Path-To-Root(v)
1 while v ≠ Nil
2   do print v
3      v ← π[v]

Answer 2

BFS и DFS принимают в качестве входных данных исходный узел.

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