DFS is not Complete
Suppose that are two connected vertices in a potentially infinite graph with a maximum branching factor of , then it's possible that DFS may not find a path connecting and .
Suppose we have the embedded graph of , but we also have a child node of which is distinct from called , then if DFS expands first, then it will never expand 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 |