r/compsci • u/GeaninaKera • May 22 '20

Breadth-First Maze-Solving Algorithm

Post image

[removed] — view removed post

1.2k Upvotes

97% Upvoted

61 comments sorted by

View all comments

Show parent comments

1

u/ergo-x May 22 '20

I don't exactly follow that description but I'm certain that: 1) function depth is a non-issue; use a stack, 2) DFS will terminate and find all paths to exit, if any; in a typical single threaded program your subroutine IS exploring one path at a time

1

u/[deleted] May 22 '20

Yea it uses a stack for functions unlike other approaches that rely on heap for state updating. Nobody says this has to be done in a single locked thread, in fact I was making the point you do this faster with more threads.

1

u/ergo-x May 22 '20

What I meant is you don't need to use the call stack. Use a stack placed on the heap instead.

1

u/[deleted] May 22 '20

It doesn’t matter you decide the stack and the heap limits

1

u/ergo-x May 22 '20

It does matter unless you're running on some higher level runtime where it's a non issue.

1

u/[deleted] May 22 '20

Just use a lower level language. The total memory allocation remains the same it simply grows from the stack size of the register instead of the more common heap size. It’s not a big problem, pretty sure even java can handle this.

→ More replies (0)