Ввод / вывод широты-первого по сравнению с глубиной поиска

Question

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

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

Я надеюсь, что я имею в виду. Спасибо!

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

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

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

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

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 и DF принимают в качестве входного узла исходного узла.

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