Depth First Search

DFS is not Complete

Suppose that

s, g

are two connected vertices in a potentially infinite graph with a maximum branching factor of

b \in N_{0}

, then it's possible that DFS may not find a path connecting

s

and

g

Suppose we have the embedded graph of

N_{0}

, but we also have a child node of

0

which is distinct from

1

called

g

, then if DFS expands

1

first, then it will never expand

g

because it will go down the infinite chain of natural numbers.

DFS Example

Assuming that we push characters onto the frontier in alphabetical order (A before B ...), specify the order of the nodes that would be explored by DFS with no cycle checking. Assume that S is the initial node, while G is the goal node.

Note that the frontier is a stack

path so far	frontier	about to explore
S	S	S
S	B, C	C
S-C	B, E	E
S-C-E	B, D	D
S-C-E-D	B	B
S-C-E-D-B	A, D, E	E
S-C-E-D-B-E	A, D, D	D
S-C-E-D-B-E-D	A, D	D
S-C-E-D-B-E-D-D	A	A
S-C-E-D-B-E-D-D-A	F	F
S-C-E-D-B-E-D-D-A-F	G	G
S-C-E-D-B-E-D-D-A-F-G