Writing a DFS with iterative deepening without recursion
-
24-01-2021 - |
質問
So currently i have a DFS with the following pseudocode
procedure DFS(Graph,source):
create a stack S
push source onto S
mark source
while S is not empty:
pop an item from S into v
for each edge e incident on v in Graph:
let w be the other end of e
if w is not marked:
mark w
push w onto S
How do I alter this function to accept a third argument that limits the depth of the search?
解決
Let Node a structure for each node of the graph, add a field called level and then:
procedure DFS(Graph,source, depth):
create a stack S
source.level = 0
push source onto S
mark source
while S is not empty:
pop an item from S into v
if v.level > depth
continue
for each edge e incident on v in Graph:
let w be the other end of e
if w is not marked:
mark w
w.level = v.level + 1
push w onto S
他のヒント
- The procedure will return
success
when an object is found. - When an object is found, the
S
will contain nodes in the path [root, source). (thesource
itself is not included.)
procedure DFS(Graph, source, depth):
StackInit(S)
if source is goal then
return success
markVisited(source)
S.push(null, source) // S is a close-list
while S is not empty then do
c, p := S.pop()
r := next(c, p) // return the next sibling of c
if r is null then
continue
S.push(r, p)
if r is marked visited then // that already marked means it cannot be goal
continue
if r is goal then
return success
markVisited(r)
if equal(depth(r), depth) then // here is what OP wants.
continue
S.push(null, r)
return fail
所属していません StackOverflow